推 oinishere: 內推我 05/16 22:02
→ JIWP: 你靠py年收百萬 05/16 22:04
推 sustainer123: 大師 05/16 22:11
推 SecondRun: 球內推 05/16 22:28
→ sixB: 你怎麼寫不一樣的 05/17 01:01
918. Maximum Sum Circular Subarray
給你一個array，請找出最大的subarray，並回傳總和
該array是一個circular array，也就是第一個元素與最後一個元素相連
subarray中每個元素只能出現一次
思路:
有兩種情況
1.最大的subarray是出現在0~n-1之間
2.最大的subarray是出現在i~n-1~0~i-1之間
第一種情況直接找max subarray就可以
第二種情況max subarray在i~n-1~0~i-1之間代表min subarray在0~n-1之間，所以求出array總和
和min subarray，兩個相減就是max subarray的值
所以就從0~n-1分別找出max subarray、min subarray、sum
回傳max sbuarray和sum-min subarray間比較大的值
還有一個特例就是所有元素都是負數，此時max subarray的值會是負數
golang code :
func maxSubarraySumCircular(nums []int) int {
curmax:=nums[0]
curmin:=nums[0]
maxsum:=nums[0]
minsum:=nums[0]
sum:=nums[0]
for _,val:=range nums[1:]{
curmax=max(val,curmax+val)
curmin=min(val,curmin+val)
maxsum=max(maxsum,curmax)
minsum=min(minsum,curmin)
sum+=val
}
if maxsum<0{
return maxsum
}
return max(maxsum,sum-minsum)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.226.253 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715868044.A.839.html