README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0053.Maximum Subarray	https://leetcode.com/problems/maximum-subarray	2024-02-23T25:04:00+08:00	2024-02-23T25:04:00+08:00	false	Kimi.Tsai	https://kimi0230.github.io/	0053.Maximum-Subarray			LeetCode Go Medium Array Dynamic Programming Blind75	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

53. Maximum Subarray

題目

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

題目大意

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），返回其最大和。

解題思路

• 這一題可以用 DP 求解也可以不用 DP。
• 題目要求輸出數組中某個區間內數字之和最大的那個值。 dp[i] 表示[0,i] 區間內各個子區間和的最大值，狀態轉移方程是dp[i] = nums[i] + dp[i-1] (dp[i- 1] > 0)，dp[i] = nums[i] (dp[i-1] ≤ 0)。

來源

• https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0053.Maximum-Subarray/
• https://leetcode-cn.com/problems/maximum-subarray/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0053.Maximum-Subarray/Maximum-Subarray.go

package maximumsubarray

// MaxSubArrayDP : DP (dynamic programming)
func MaxSubArrayDP(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	if len(nums) == 1 {
		return nums[0]
	}

	dp, res := make([]int, len(nums)), nums[0]
	dp[0] = nums[0]

	for i := 1; i < len(nums); i++ {
		if dp[i-1] > 0 {
			// 前一個和是正的 繼續加下去
			dp[i] = nums[i] + dp[i-1]
		} else {
			// 前一個和是小於等於0 直接拿現在值取代
			dp[i] = nums[i]
		}
		res = max(res, dp[i])
	}
	return res
}

// MaxSubArray1 : 模擬, 比DP快
func MaxSubArray1(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	maxSum := 0
	tmp := 0
	for i := 0; i < len(nums); i++ {
		tmp += nums[i]
		if tmp > maxSum {
			maxSum = tmp
		}
		if tmp < 0 {
			tmp = 0
		}
	}
	return maxSum
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

//TODO: 分治法�, 這個分治方法類似於「線段樹求解最長公共上升子序列問題」的pushUp操作