# 题目链接
# 题目描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3
2
3
# 解题思路
主要是寻找状态转义方程和确定dp[i]的含义 最初我的想法是让dp[i]等于nums[i]之前的最大和 但是因为题目中要求必须数组是连续的，如果这样做的话我无法判断前面是否连续 又设dp[i]是以i结尾的数组最大和，这样子得到的就是连续的了
func maxSubArray(nums []int) int {
dp:=make([]int,len(nums))
for i,_:=range dp{
dp[i]=nums[i]
}
for i:=1;i<len(dp);i++{
if dp[i]+dp[i-1]>dp[i]{
dp[i]=dp[i]+dp[i-1]
}
}
max:=dp[0]
for i,_:=range dp{
if dp[i]>max{
max=dp[i]
}
}
return max
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18