[算法] leetcode 53.最大子数组和 golang

题目

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

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

 

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

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

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
 

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解法1: 贪心算法

思路

通过上一个位置的最大和求当前最大和(当前位置最大和为负,当前位置最大和重置为0)

举例

数组下标	当前值	上一个最大和	当前最大和	总最大和	提示
0	-2	0	-2	0	当前位置最大和为负,当前位置最大和重置为0
1	1	0	1	1
2	-3	1	-2	1	当前位置最大和为负,当前位置最大和重置为0
3	4	0	4	4
4	-1	4	3	4
5	2	3	5	5
6	1	5	6	6
7	-5	6	1	6
8	4	1	5	5

最后返回总的最大和 6

代码

//最大子数组和
func maxSubArray(nums []int) int {
	//总的最大和
	totalMax := 0
	//前一个位置的最大和
	prevMax := 0
	for i := 0; i < len(nums); i++ {
		//求当前位置最大和
		currentMax := prevMax + nums[i]
		//如果当前位置最大和小于0重置为0
		if currentMax < 0 {
			prevMax = 0
		} else {
			//如果当前位置最大和大于0,更新
			prevMax = currentMax
			//如果当前位置最大大于总的最大和更新总的最大和
			if currentMax > totalMax {
				totalMax = currentMax
			}
		}
	}
	return totalMax
}

测试

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

//最大子数组和
func TestP1(t *testing.T) {
	cases := []struct {
		arr    []int
		expect int
	}{
		{
			arr:    []int{-2, 1, -3, 4, -1, 2, 1, -5, 4},
			expect: 6,
		},
		//空数组
		{
			arr:    nil,
			expect: 0,
		},
		//负数
		{
			arr:    []int{-1, -2},
			expect: -1,
		},
		//负数
		{
			arr:    []int{-1},
			expect: -1,
		},
	}
	for _, c := range cases {
		actual := maxSubArray2(c.arr)
		assert.Equal(t, c.expect, actual)
	}
}

解法2: 动态规划

思路

前一个元素大于0, 则将其加到当前元素上

代码

func maxSubArray2(nums []int) int {
	if len(nums) == 0 {
		fmt.Printf("%s\n", "err: 参数长度为0")
		return 0
	}
	prevMax := 0
	for i := 0; i < len(nums); i++ {
		if prevMax >= 0 {
			nums[i] += prevMax
		}
		prevMax = nums[i]
	}
	//遍历求最大值
	totalMax := nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] > totalMax {
			totalMax = nums[i]
		}
	}
	return totalMax
}

reference

53. 最大子数组和 - 力扣（LeetCode） (leetcode-cn.com)