链接：
Maximum Subarray

题意：给定一串字符串a[1...n]，找出一个字串a[i...j](0 <=i < j <=n),使子串a[i...j]的和最大。

#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

int maxSubArray(vector<int>& nums)
{
    int maxSum = nums[0], tSum = 0;
    for(int i = 0; i < nums.size(); i++)
    {
        tSum += nums[i];
        maxSum = max(tSum, maxSum);
        tSum = max(0, tSum);  //如果是负数就重新计算sum
    }
    return maxSum;
}

int main()
{
    vector<int> nums;
    int n, x;
    cin>>n;
    for(int i = 0; i < n; i++)
    {
        cin>>x;
        nums.push_back(x);
    }
    cout<<maxSubArray(nums);
    return 0;
}