问题描述：
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
解题思路：
简单的动态规划题目：
- 创建 dp[len(nums)]，其中 dp[i] 表示以 i 位置结尾的数的最大子段和；
- 状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])； - 最后，max(dp) 就是最终的答案。
时间复杂度为O(n)，空间复杂度也为O(n)。
Python3 实现：
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], dp[i-1] + nums[i])
return max(dp)
补充：
最小子段和问题可以转化为最大字段和问题，只需要将列表中的元素全部取反，然后求最大字段和，再将结果取反即可。
改进——解题思路2：
可以不用列表，只需要两个变量，一个记录局部最大子段和，一个记录全局最大子段和。当局部最大子段和大于0时，就累积当前的数字；否则，就把当前的数字作为当前最大子段和。每次循环判断之后，还要更新最大子段和的值。这样时间复杂度仍为 O(n)，但空间复杂度将为 O(1)。
Python3 实现2：
# 动态规划
class Solution:
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ret = nums[0] # 全局最大
tem = 0 # 局部最大
for i in range(len(nums)):
if tem > 0:
tem += nums[i]
else:
tem = nums[i]
ret = max(ret, tem)
return ret
a = [-2,1,-3,4,-1,2,1,-5,4]
b = Solution()
print(b.maxSubArray(a)) # 6 # [4,-1,2,1]
