minimum subarray:: O(N), O(1)

solution
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 ์ดํ•˜๋กœ ๋–จ์–ด์ง„ ์ดํ›„์—” 
max sub array sum

// 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