leetcode53之最大子序和

题目描述：

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray

 1 def maxSubArray(nums):
 2     '''
 3     找出和最大的连续子数组，返回和，动态规划策略
 4     :param nums:
 5     :return:
 6     '''
 7     pre = 0  # 表示当前元素结尾的子数组之和
 8     tmp_res = []  # 存放当前元素结尾的子数组之和
 9     for num in nums:
10         pre = max(pre + num, num)
11         tmp_res.append(pre)
12 
13     return max(tmp_res)
14 
15 
16 print("----------测试maxSubArray()----------")
17 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
18 res = maxSubArray(nums)
19 print("res=", res)
20 
21 
22 def maxSubArray1(nums):
23     '''
24     找出和最大的连续子数组，返回和，动态规划策略
25     :param nums:
26     :return:
27     '''
28     pre = 0  # 表示当前元素结尾的子数组之和
29     # tmp_res = []  # 存放当前元素结尾的子数组之和
30     maxAns = 0  # 表示子数组最大值
31     for num in nums:
32         pre = max(pre + num, num)
33         maxAns = max(maxAns, pre)
34         # tmp_res.append(pre)
35 
36     return maxAns
37 
38 
39 print("----------测试maxSubArray1()----------")
40 nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
41 res = maxSubArray1(nums)
42 print("res=", res)

输出：

----------测试maxSubArray()----------
res= 6
----------测试maxSubArray1()----------
res= 6

总结：本题采用动态规划求解。上述两种方式均为动态规划求解结果，只不过在最大值更新过程稍微有点区别.

本题中的动态规划思想：循环遍历该数组，求出以每个元素结尾的最大连续子数组之和f(i)，显然我们要求的结果就是maxf(i),i=0,1,2....L-1(L 为整个数组长度)。问题是如何求解f(i)，可以发现，f(i)只与当前元素num[i]和f(i-1)有关，

可写作f(i)=max(f(i-1)+num[i],num[i])，说明如下：

如果f(i-1)>0，那么对增大f(i)有效，f(i)=f(i-1)+nums[i]

如果f(i-1)<=0，那么对增大f(i)无效，f(i)=nums[i]

在实现过程中，可以先将各元素结尾子数组之和存储在统一数组中，然后求该数组最大值即可，即为方法1的具体实现过程

也可以设置变量maxAns表示当前遍历过的子数组最大值，每次遍历之后动态更新值即可，即为方法2的具体实现过程

两种方法殊途同归，只不过在时空复杂度上稍有不同。方法1时间O(n),空间O(n),方法2时间O(n),空间O(1)