连续子数组最大和

方法1:归纳法

int maxSubArray(vector<int> nums) {
    if (nums.empty()) return 0;
    int curSum = 0;
    int maxSum = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (curSum <= 0)
            curSum = nums.at(i);
        else
            curSum += nums.at(i);
        if (curSum > maxSum)
            maxSum = curSum;
    }

    return maxSum;
}

方法2:动态规划

int maxSubArray(vector<int> &nums)
{
    if (nums.empty()) return 0;
    int ans = INT_MIN;
    vector<int> dp(nums.size());
    dp[0] = nums[0];
    ans = dp[0];
    for (int i = 1; i < nums.size(); i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        ans = max(ans, dp[i]);
    }
    return ans;
}