动态编程 - 子阵列系列 - 最大子阵列和

1.题目解析

 题目来源：53.最大子数组和——力扣

 测试用例

2.算法原理

1.状态表示

dp[i]:以第i个位置为结尾的数组所有子数组之和的最大值

2.状态转移方程

此时对dp[i]的填值有两种情况

1.以当前位置本身的数为子数组，则子数组之和就是该数

2.以当前位置之前的所有数为子数组但不包括当前数，求出前面子数组的总和

对于dp[i]来说需要取二者的较大值

3.初始化

由于填表时需要使用到前一个数，所以需要初始化第一个数，但是可以设置虚拟位置来简单化，虚拟位置的值置为0避免影响后续的填表

4.填表顺序

从左到右

5.返回值 

返回dp表中最大的值即可

3.实战代码

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