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.

刷到这道题的时候我想起来原来在理工大读书的时候有门课叫算法设计与分析，当时有个0 1背包问题，虽然当时不会写代码，但也对DP（动态规划）算法留下了心理阴影。
尝试使用两种两种解法来解决该问题：

解法一

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0;
        int max = INT_MIN;
        int numsSize = nums.size();

        for(int i = 0;i < numsSize;i++)
        {
            if(sum > 0)
                sum = sum +nums[i];
            else 
                sum = nums[i];

            if(sum > max)
                max = sum;
        }

        return max;
    }
};

解法二

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();

        //dp[i]保存计算的结果
        int *dp = new int[n];
        
        dp[0] = nums[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = std::max(max, dp[i]);
        }
        
        return max;
    }
};

上面两种解法中，方法一看着简单，但确不好理解，方法二是正儿八经的动态规划解法，实质上方法一 与方法二相同。
动态规划
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
将任务分解，递进关系为：

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) + A[i] :A[i]; 

如果是求解数组A中序列[0,i]的最大值，如果[0,i-1]大于0，那么将[0,i-1]的最大值加上A[i]的值，否则如果[0,i-1]的值是负的，那么我们重头来过，这里的逻辑，不就和解法一种的逻辑一致吗？

if(sum > 0)
    sum = sum +nums[i];
else 
    sum = nums[i];

我们方法二种通过std::max函数计算最大值，其实就是方法一中的

if(sum > max)
    max = sum;

我们以{-2,1,-3,4,-1,2,1,-5,4}为例，演示计算dp的过程：
初始时dp[0]=-2,然后根据上面公式dp[1]判断dp[0]>0不成立，因此dp[1]=1,然后dp[2]判断dp[1]大于0成立，dp[2]=dp[1]+a[2]=1+-3 = -2，依次类推，可以得到如下dp值：

arr = {-2,1,-3,4,-1,2,1,-5,4}
dp  = {-2,1,-2,4,3,5,6,1,5}

实际上是求解dp中的最大值，然后我们将两者合并到一个循环里。
DP算法看似简单，在很多情形下和递归一样，即使你知道要用递归算法，但真正写起来会有种无从下手的感觉，这些还需要在工作中慢慢积累和体会。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];

        vector<int> dp(n,0);
        dp[0]=nums[0];
        int maxsum = nums[0];
        for(int i = 1;i<n;i++)
        {
            dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1]:0);
            maxsum = max(maxsum,dp[i]);
        }

        return maxsum;
    }
};

上面的算法其实还可以继续优化，存储空间不需要O(n)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp0 = nums[0],dp1 = 0;
        int maxsum = nums[0];

        for(int i = 1;i < n;i++)
        {
            dp1 = nums[i] + (dp0 > 0 ? dp0:0);
            maxsum = max(maxsum,dp1);
            dp0 = dp1;
        }
        return maxsum;
    }
};

2021-12-25更新

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size,0);
        dp[0] = nums[0];
        int maxsub = dp[0];
        for(int i = 1;i < size;i++)
        {
            dp[i] = ((dp[i-1] >0) ? dp[i-1]:0)+ nums[i];
            maxsub = max(maxsub,dp[i]);
        }

        return maxsub;
    }
};

这里使用动态规划的一个难点是动态方程的写法以及含义，这里我们约定dp[i]表示以下标i结尾的最大子数组和，因此 dp[i] = ((dp[i-1] >0) ? dp[i-1]:0)+ nums[i];这里必须要加上nums[i，因为必须以nums[i]结尾，如果以i-1结尾的和大于0我们就把这个结果相加。