0. 前言

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.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1. c++版本

思想: 状态转移方程：dp[i] = max{num[i], dp[i-1] + num[i]}

    int maxSubArray(vector<int>& nums) {
        if (nums.empty())
            return 0;
        int sum = nums[0], maxSum = sum;
        for (int i=1; i< nums.size(); ++i) {
            sum =  sum >= 0 ? sum + nums[i] : nums[i];
            maxSum = max(sum, maxSum);
        }
        return maxSum; 
    }

2. python版本

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        current_sum, max_sum = nums[0], nums[0]
        for i in range(1, len(nums)):
            current_sum =  current_sum + nums[i] if current_sum >=0 else nums[i]
            max_sum = max(current_sum, max_sum)
        return max_sum