未分類

Maximum Subarray

Array, DivideAndConquer, DynamicProgramming, Go, LeetCode

Maximum Subarray

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.

提示 解題應用
Array Array/Slice
DynamicProgramming 規律觀查

Default:

1
2
3
func maxSubArray(nums []int) int {
}

解答思路:

一開始是用兩個變數去指向要找出結果陣列(最大值的陣列)的開頭與結尾，不過後來發現到只需要求總合即可，所以便不需要去紀錄陣列的位置，直接遍歷陣列找出最大總合即可，每當從陣列取出一個新值，如果先前的總合為負數，就直接將該值取代總合(當作最大值陣列的開頭)，因為如果包含先前總合的話，不論目前取出的該值為正或為負一定會變的更小，所以倒不如就直接取代以尋找新的陣列組合，至於如果先前總合不為負數則可以繼續往下累加以尋找總合最大值，每次確定當下的總合之後便判斷是否比目前找到的最大總合大，如果是就取代直到取完陣列的所有值後才回傳最大值的總合。

程式碼解說:

一開始先將總合與最大總合初始化為陣列的第一個元素值，之後才開始以迴圈從陣列的第二個值一個個取值，如思路所寫如果先前總合為負的話就將目前取出的值取代總合，否則就將該值繼續累加至總合之中，待確定當下的總合之後便判斷是否比目前找到的最大總合大，如果是就取代直到取完陣列的所有值後才回傳最大值的總合

1
2
3
4
5
6
7
8
9
10
11
12
13
sum := nums[0]
max := sum
for _, v := range nums[1:] {
	if sum < 0 {
		sum = v
	} else {
		sum += v
	}
	if sum > max {
		max = sum
	}
}
return max

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxSubArray(nums []int) int {
	sum := nums[0]
	max := sum
	for _, v := range nums[1:] {
		if sum < 0 {
			sum = v
		} else {
			sum += v
		}
		if sum > max {
			max = sum
		}
	}
	return max
}

總結:

要從一陣列中找出子陣列能組出的最大總合，其做法是每當從陣列取出一個新值，如果先前的總合為負數，就直接將該值取代總合(當作最大值陣列的開頭)，至於如果先前總合不為負數則可以繼續往下累加以尋找總合最大值，每次確定當下的總合之後便判斷是否比目前找到的最大總合大，如果是就取代直到取完陣列的所有值後才回傳最大值的總合。

分享到