[leetcode] week1 - Maximum Subarray

 

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/528/week-1/3285/

Account Login - LeetCode

 

어려워서 검색해보니 위키에 간단하게 소개가 돼 있었다. : Maximum_subarray_problem

2차원 배열 bruth-force : O(n6) 
수식을 사용해서 1차원 배열 bruth-force로 해결 : O(n2) - 내가 생각했던 수준ㅠㅠ
devide-and-conquer : O(n log n) 
kanade 알고리즘 : O(n)

leetcode가 아래처럼 얘기를 한 걸 보면 이 문제는 devide and conquer를 연습하기 위한 문제인가부다..

둘다 해보자!

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1) kanade algorithm

아래 동영상을 참고해봤다.

https://www.youtube.com/watch?v=86CQq3pKSUw&feature=youtu.be

O(n2) 풀이 : 
A[a1, a2, a3, ... , aN] 배열이 있으면
각 index까지의 부분 배열의 합 중에 가장 큰 부분 배열을 구한다
ex) 3번째 index까지 부분 배열을 구하면
[a1], [a1, a2], [a1, a2, a3] 인데 이 중에 가장 합이 큰 배열을 구한다.

kanade algorithm 풀이 :
A[a1, a2, a3, ... , aN] 배열이 있으면 
1) j번째에서 aj의 크기와 a1, .. aj까지의 합을 비교해서 둘 중 큰 것을 선택한다 (나머지 부분 배열은 무시)
-> max_subsum = max(aj, sum(a1, aj))
2) j번째까지 전체 max와 j번째까지 부분배열의 max를 비교해서 전체 max를 바꾼다.
-> max_sum과 max_subsum 비교
3) 첫번째는 a1으로 고정됨.

결국 처음부터 끝까지 탐색을 하면서 가장 합이 큰 배열을 유지하면서
새로 추가되는 j번째 원소를 추가했을 때 기존보다 합이 더 커지면 부분 배열을 늘리고 
추가하지 않는 게 더 크면 기존 부분배열을 유지하는 방법이다.

코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum = nums[0]
        max_subsum = nums[0]
        for i in range(1,len(nums)): 
            max_subsum = max(max_subsum + nums[i], nums[i])
            if max_subsum >= max_sum:
                max_sum = max_subsum
        return max_sum

O(n)이라 그런가 7% 안에 들었다

예전에 알게된 알고리즘이었는데 이제서야 조금 이해가 간다

ㅠㅠ

 

2) Divide-and-conquer_algorithm

이번엔 넘나 유명한 책인 Introduction to Algorithms을 참고해봤다.

(예전에 배웠는데 지금은 까먹은거보면 역시 필요할 때 배우지 않으면 기억이 안난다)

 

Divide and Conquer는 문제의 최적화된 답을 찾기 위해서 아래처럼 푸는 방법을 말한다.

1. 문제를 작은 문제(subproblem) 2개나 그 이상으로 쪼갠다.(풀기 쉽게 쪼갬)

2. 작은 문제를 푼다

3. 푼 것을 합친다.

ex) n개의 정수를 오름차순 정렬한다.
n개 -> n/2개로 나누어서 2 뭉치를 만든다(1.) --> 1개만 남을 때까지 이걸 계속 반복한다
1개 -> 2개 -> 4개로 합칠 때(3.) 1개끼리 비교해서 작은 것이 앞으로 오도록 정렬한다(2.)

Introduction to Algorithms에서는 배열 A를 두 배열 B, C로 쪼개서

A의 최대배열이 B에 있을 때, C에 있을 때, B와 C 모두에 걸쳐 있을 때(D)로 3가지 경우를 나누어서 풀었다.

Devide : 배열을 B, C, D로 나누어 각 그룹에서 최대 배열을 찾는다.

Conquer : B, C, D 배열의 최대값을 비교해서 가장 큰 값을 찾는다.

부분배열 A[low, .., high]의 최대 부분배열을 구한다고 가정해보자.
(Divide and conquer에서는) 이 A배열을 가능하면 같은 크기로 배열을 나눈다. 
-> 나누는 기준인 midpoint를 알 수 있고(=mid) 배열을 이렇게 나눌 수 있다.

A = B + C, B[low, ... mid], C[mid+1, ... high]

-> A의 최대 부분배열은 B, C 중 한 곳에 반드시 놓이게 된다. 둘 다 놓일 수도 있고.
-> A의 최대 부분배열을 찾는 것의 부분문제로 B의 최대 부분배열과 C의 부분배열도 재귀적으로 찾을 수 있다.
그리고 midpoint를 포함하는 부분배열 D의 최대 부분배열을 구해서 B, C, D 중 제일 큰 것을 찾으면 된다.

이 책에서는 D를 찾기 위해 Find-Max-Crossing-Subarray라는 절차를 생각해냈는데

(배열 A, low, mid, high)를 input으로 받고

mid point를 지나는 부분배열의 최대 부분배열의 정보를 리턴한다.

FIND-MAX-CROSSING-SUBARRAY - O(n) : (A, low, mid, high) 
left-sum = -∞
sum = 0
for i = mid downto low
  sum = sum + A[i]
  if sum > left-sum
    left-sum = sum
    max-left = i
right-sum = -∞
sum = 0
for j = mid+1 to high
   sum = sum + A[j]
   if sum > right-sum
     right-sum = sum
     max-right = j
return (max-left, max-right, left-sum+right-sum)

1) 첫번째 for : B[low, ... mid]에서 mid -> low로 내려갈 때 가장 큰 부분배열합을 구한다.

2) 두번째 for : C[mid+1, ... high]에서 mid+1 -> high로 올라갈 때 가장 큰 부분배열합을 구한다.

3) return : 1)과 2)를 합치면 mid를 지나는 가장 큰 부분배열합의 정보를 알 수 있다.

 

그 다음에는 본래 목적인 Find Maximum subarray 절차를 따른다.

여기에 Divide and Conquer 알고리즘이 들어가 있음.

B와 C의 최대 부분배열은 이 절차를 재귀적으로 따르면 되지만 D는 이 절차에 포함되지 않아서

위의 Find-Max-Crossing-Subarray를 만든 듯.

FIND-MAXIMUM-SUBARRAY - O(lgn) : (A, low, high)
if high == low
  return (low, high, A[low]) // base case: only one element
else 
  mid = [(low + high)/2]
  (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
  (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid, high)
  (cross-low, cross-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
 
  if left-sum >= right-sum and left-sum >= cross-sum
    return (left-low, left-high, left-sum)
  elseif right-sum >= left-sum and right-sum >= cross-sum
    return (right-low, right-high, right-sum)
  else 
    return (cross-low, cross-high, cross-sum)

 

합친 코드

def findMaxCrossingSubArray(arr, low, mid, high):
    left_sum = min(arr[low:mid+1])
    sub_sum = 0
    max_left = 0
    for i in range(mid, low-1, -1):
        sub_sum += arr[i]
        if sub_sum > left_sum:
            left_sum = sub_sum
            max_left = i       
    right_sum = min(arr[mid+1:high+1])
    sub_sum = 0
    max_right = 0
    for j in range(mid+1, high+1):
        sub_sum += arr[j]
        if sub_sum > right_sum:
            right_sum = sub_sum
            max_right = j  
    return (max_left, max_right, left_sum + right_sum)

def findMaximumSubarray(arr, low, high):
    if low == high:
        return (low, high, arr[low])
    else:
        mid = (low+high)//2
        left_low, left_right, left_sum = findMaximumSubarray(arr, low, mid)
        right_low, right_right, right_sum = findMaximumSubarray(arr, mid+1, high)
        cross_low, cross_right, cross_sum = findMaxCrossingSubArray(arr, low, mid,high)
        if left_sum >= right_sum and left_sum >= cross_sum:
            return (left_low, left_right, left_sum)
        elif right_sum >= left_sum and right_sum >= cross_sum:
            return (right_low, right_right, right_sum)
        else:
            return (cross_low, cross_right, cross_sum)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_low, max_right, max_sum = findMaximumSubarray(nums, 0, len(nums)-1)
        return max_sum

 

 

 

아래 사이트에서도 자세히 나와있다

https://www.geeksforgeeks.org/maximum-subarray-sum-using-divide-and-conquer-algorithm/