LeetCode-53.最大子数组和 - sheep44044的小站

数组#

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

子数组是数组中的一个连续部分。

示例 1：

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

示例 2：

1
输入：nums = [1]
2
输出：1

示例 3：

1
输入：nums = [5,4,-1,7,8]
2
输出：23

AI优化后的答案

优雅

思路：前缀和+数组

1
func maxSubArray(nums []int) int {
2
    sum := 0
3
    maxsum := -10001
4
    minsum := 0
5

6
    for _, num := range nums {
7
        sum += num
8

9
        maxsum = max(maxsum, sum-minsum)
10

11
        minsum = min(minsum, sum)
12
    }
13

14
    return maxsum
15
}

自己的答案

有点丑陋了这个答案，虽然是手撕

1
func maxSubArray(nums []int) int {
2
    sum := 0
3
    maxsum := -10001
4
    minnum := 10001
5
    m := []int{0}
6

7

8
    if len(nums) == 1 {
9
        return nums[0]
10
    }
11

12
    for i := 1; i <= len(nums); i++ {
13
        minnum = min(minnum, m[i-1])
14
        sum += nums[i-1]
15
        m = append(m, sum)
16

17
        maxsum = max(maxsum, m[i]-minnum)
18
    }
19

20
    return maxsum
21
}

一个204/210正确的答案

超时了，可惜…纪念一下逝去的暴力法

1
func maxSubArray(nums []int) int {
2
    sum := 0
3
    maxsum := -10001
4
    m := []int{0}
5

6

7
    if len(nums) == 1 {
8
        return nums[0]
9
    }
10

11
    for i := 1; i <= len(nums); i++ {
12
        sum += nums[i-1]
13
        m = append(m, sum)
14

15
        for j := 0; j < i; j++ {
16
            maxsum = max(maxsum, m[i]-m[j])
17
        }
18

19
    }
20

21
    return maxsum
22
}