leetcode

题目链接
Description
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

解题思路
遍历数组，使用maxn保存目前为止最大连续和，pre保存包含nums[i-1]的最大连续和。遍历过程中若nums[i]>pre+nums[i],则pre=nums[i],否则pre=nums[i]+pre。

示例代码

int maxSubArray(vector<int>& nums) {
    int maxn = 0;
    int pre = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        if ((pre + nums[i]) >= nums[i])
            pre = pre + nums[i];
        else
            pre = nums[i];
        maxn = max(pre, maxn);
    }
    cout << maxn << endl;
    return maxn;
}