题解 | #最大和的子数组#

思路：题目要求，子数组在原数组中连续，那么假设dp[i]表示在数组中第i个位置处的最大值，那么dp[i]的得来有两种可能：1、前面的累加+数组当前位置的值（即dp[i-1]+A[i]）；2、摒弃掉前面的数字，只要当前位置的值（即A[i]）。只要找这两种可能中的最大值，就是dp[i]的值。
为什么只有这两种可能呢？首先是题目要求子数组连续，那么要想有最大值，要么是前面的一串数字加上当前A[i]的值仍然比前面的一串数字和大，那么此时的子数组就会延续一位；要么就是加上当前数字之后值小于前面的一串数字和，那么就要舍弃掉前面的数字，从当前数字重新开始。
找这两种可能中的较大值作为dp[i]的值，然后将dp[i]的值和之前单独记录的最大值作比较，以进行最大值的更新。
代码如下：

#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     * 
     * @param A int整型一维数组 
     * @param n int A数组长度
     * @return int整型
     */
    int maxSubArray(int* A, int n) {
        // write code here
        int max_value = A[0];
        int dp[n];
        dp[0] = A[0];
        for(int i=1;i<n;i++)
        {
            dp[i]=max(dp[i-1]+A[i],A[i]);
            max_value=max(max_value,dp[i]);
        }
        return max_value;
    }
};