最大子序和-53

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [0]
输出：0

示例 4：

输入：nums = [-1]
输出：-1

示例 5：

输入：nums = [-100000]
输出：-100000

提示：

• 1 ≤ nums.length ≤ 3 * 10
• -10 ≤ nums[i] ≤ 10

思路

我们创建一个dp[]数组，里面的值含义是：到当前位置为止，最大的子序列和是多少。

• 当数列只有 1 个元素时，dp[0] = nums[0]；

• 当数列有 2 个元素时，dp[1] = max( dp[1-1]+nums[1], nums[1] )，意思是：
  有当遇到第二个元素时，有2个选择：选或不选：

  • 选：int take_it =dp[1-1] + nums[1]；
  • 不选：int no_take = nums[1]；
  • 在这两个里面选最大的来作为当前dp[i]的值；
• 当数列有 i 个元素时： %20%3D%20%0A%5Cbegin%7Bcases%7D%0Anums%5Bi%5D%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20nums%5Bi%5D%20%2B%20dp(i-1)%5C%20%2C%5C%20nums%5Bi%5D%20%5C%7D%2C%20%26%20i%20%5Cge%201%0A%5Cend%7Bcases%7D%0A#card=math&code=dp%28i%29%20%3D%20%0A%5Cbegin%7Bcases%7D%0Anums%5Bi%5D%2C%20%26i%20%3D%200%5C%5C%0Amax%5C%7B%5C%20nums%5Bi%5D%20%2B%20dp%28i-1%29%5C%20%2C%5C%20nums%5Bi%5D%20%5C%7D%2C%20%26%20i%20%5Cge%201%0A%5Cend%7Bcases%7D%0A)

有了状态转移方程，我们能求出各阶段dp[]的值。结果返回dp[]数组里最大的那个元素。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size() == 1)   return nums[0];
        int* dp = new int[ nums.size() ];
        dp[0] = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            int take_it = dp[i-1] + nums[i];
            int no_take = nums[i];
            dp[i] = take_it > no_take ? take_it : no_take;
        }
        int MAX = *max_element(dp, dp + nums.size());
        delete[] dp;
        return MAX;
    }
};