连续子数组的最大和（Python and C++解法）

题目：

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

示例1:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof

思路：

　　使用动态规划解决。

　　状态定义：dp[i]代表以元素num[i]为结尾的连续子数组的最大和。

　　转移方程：若 dp[i-1] ≤0 ，说明 dp[i - 1] 对 dp[i] 产生负影响，即此时dp[i-1] + nums[i] < nums[i]。

　　　　　　　当 dp[i - 1] > 0时：执行 dp[i] = dp[i-1] + nums[i]；
　　　　　　　当 dp[i - 1] ≤0 时：执行 dp[i] = nums[i]；

　　注意：由于dp[i]与nums[i]有关，故动态规划可以在数组本身进行，空间复杂度降至O（1），但是考虑到原数组有可能不被允许修改，所以定义变量存储dp[i]，dp[i-1]和最大值。

Python解法：

 1 class Solution:
 2     def maxSubArray(self, nums: List[int]) -> int:
 3         maxSum = nums[0]  # 最大值初始化为第一个元素
 4         predpi = -1  # 记录dp[i-1]，初始化为一个负值
 5         curdpi = nums[0]  # 记录当前dp[i]
 6         for num in nums:
 7             if predpi <= 0:
 8                 curdpi = num  
 9             if predpi > 0:
10                 curdpi = predpi + num
11             if curdpi > maxSum:
12                 maxSum = curdpi  #  更新最大子数组的和
13             predpi = curdpi  # 更新dp[i]
14         return maxSum

C++解法：

 1 class Solution {
 2 public:
 3     int maxSubArray(vector<int>& nums) {
 4         int maxSum = nums[0];  // 最大值初始化为第一个元素
 5         int predpi = -1;  // 记录dp[i-1]，初始化为一个负值
 6         int curdpi = nums[0];  // 记录当前dp[i]
 7         for(int num: nums) {
 8             if(predpi <= 0)
 9                 curdpi = num;
10             if(predpi > 0)
11                 curdpi = predpi + num;
12             if(curdpi > maxSum)
13                 maxSum = curdpi;  // 更新最大子数组的和
14             predpi = curdpi;
15         } 
16         return maxSum;
17     }
18 };