Re: [閒聊] 每日leetcode已回收
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
推
05/16 22:02,
1年前
, 1F
05/16 22:02, 1F
→
05/16 22:04,
1年前
, 2F
05/16 22:04, 2F
推
05/16 22:11,
1年前
, 3F
05/16 22:11, 3F
推
05/16 22:28,
1年前
, 4F
05/16 22:28, 4F
→
05/17 01:01,
1年前
, 5F
05/17 01:01, 5F
討論串 (同標題文章)
完整討論串 (本文為第 229 之 1554 篇)：