题目描述

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.

解题思路

动态规划思想

以nums数组[-2,1,-3,4,-1]为例

• dp[0]为-2
• dp[1] = max(dp[0]+nums[1],1)=max(-2,1)=1
• dp[2] = max(dp[1]+nums[2],-3)=max(1-3,-3)=-2
• 当前的sum为dp[i-1]+nums[i], nums[i]最大值
• 然后将maxSum和sum进行比较，取最大值

Go代码实现

Go代码实现1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func (a int, b int)int  {
	if a>b {
		return a
	}else{
		return b
	}
}
func maxSubArray(nums []int) int {
	n := len(nums)

	if n == 0 {
		return 0
	}

	if n == 1 {
		return nums[0]
大专栏