minimum subarray:: O(N), O(1)
def maximum_circular_subarray(arr):
max_subarray_sum_wraparound = sum(arr) - min_subarray_sum(arr)
return max(max_subarray_sum(arr), max_subarray_sum_wraparound)
def max_subarray_sum(arr):
max_ending_here = max_so_far = 0
for x in arr:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
def min_subarray_sum(arr):
min_ending_here = min_so_far = 0
for x in arr:
min_ending_here = min(x, min_ending_here + x)
min_so_far = min(min_so_far, min_ending_here)
return min_so_far
min_subArray_sum
์ฐ์์ ์ผ๋ก ์ด๋ฃจ์ด์ง subArray ์ค ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฐ์ง ๋ถ๋ถ์ ๋ ๋ ค ๋ฒ๋ฆฌ๋ฉด?
[5, -1, -2, -5, -1, 6]
// max sub array
[5, 4, 2, -3, -1, 6]
6 ์ด ๊ฐ์ฅ ํฐ sub array sum ์ด๋ค
๊ฐ์ด 0 ์ผ๋ก ๋จ์ด์ง๊ธฐ ์ ์๋ ์ฐ์ํ๋ current Sum ์ ๊ตฌํด์ฃผ๊ณ
๊ฐ์ด 0 ์ดํ๋ก ๋จ์ด์ง ์ดํ์

// min sub array
[0, -1, -3, -8, -9, -3]
-9 ์ด ์๋ฏธํ๋ ๋ฐ๋ [-1, -2, -5, -1] ์ ํฉ์ด๊ณ ์ด sub array๊ฐ ์ด ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ํฉ์ ํ์ฑํ๋ค.
-9 ๊ฐ ์์์ด๊ธฐ ๋๋ฌธ์ ์ด ๊ฐ์ total sum์์ ๋นผ๋ฉด
2 - (-9) = 11 ๋ก ์ต๋ ๊ฐ์ ๊ฐ์ง๋ circular sub array [6] -> [5]๋ฅผ ๊ตฌํ ์ ์๋ค.
// extra
-9 ๊ฐ ์๋๋ผ 1 ์ด๋ฉด
2 - 1 = 1 ์ด๊ธฐ ๋๋ฌธ์ ์ด ๊ฐ์ด ์ต๋ sub array ํฉ์ด ์๋ ์ ์๋ค.
๊ทธ๋์ ๊ทธ๊ฒ์ ํ์ธํ๊ธฐ ์ํด
max_subarray_sum_wraparound = sum(arr) - min_subarray_sum(arr)
max(max_subarray_sum(arr), max_subarray_sum_wraparound)
max (max_subarray_sum, total - ์ต์ ํฉ์ ๋ํ๋ด๋ ๊ตฌ๊ฐ sub array)
์ผ๋ก ๋ง์ง๋ง ๋ณ์๋ฅผ ์ฒดํฌ ํ๋ค
์ต์ ํฉ์ ๋ํ๋ด๋ ๊ตฌ๊ฐ sub array => ์์์ผ ๊ฒฝ์ฐ ํ์ธ ์ฉ
Last updated