[Hackerrank] [Hard] Maximum Subarray Sum

https://www.hackerrank.com/challenges/maximum-subarray-sum/problem

Maximum Subarray Sum | HackerRank

풀이

• Input : 숫자 배열 arr, 나눌 수 m
• subarray : arr[ i : j ] index i부터 j까지 연속된 배열
• 문제 : subarray의 수를 다 더하고, m으로 나누었을 때 나머지의 최댓값 구하기.
• 모든 경우의 수를 다 해보는 O(N^2) 은 당연히 timeout
• $P_{i}$ : 0 ~ i번째 index까지 수를 더한 뒤, m으로 나누었을 때의 나머지
• $S_{i+1, j}$ : arr의 index ( i + 1)에서 j 까지의 subarray 합을 구한 뒤 M으로 나눴을 때의 나머지
  • $S_{i+1, j} = (P_j - P_i + M)\%M$

  • 

  • 왜 저 식이 동작하는지는 직접 구해보면 알수 있음.

  • 

  • $P_j - P_i$ 에 M 을 더해줌으로써 결과가 항상 양수가 되도록 함.( M%M 을 하게 되면 0이기 때문에 더해줘도 상관 없음. )
• 위 식에서 나올 수 있는 최댓값을 생각해내는게 어려웠음.
  • 언제 최대? $P_j - P_i = -1$ 일 때, $P_j - P_i + M = M-1$ 이 되므로, 나머지가 $M-1$ 로 최대가 되고, -1이 아니라면, $P_i가 P_j$ 보다 바로 다음 큰 수가 되면 됨. 이 부분은 아래 코드에서 bisect 라이브러리를 사용해 구현.

def maximumSum(arr, mod):
    import bisect
    # p_i를 정렬해서 저장.
    sort_p_i = []
    result = 0
    cur = 0
    for i in range(len(arr)):
        # P_i를 계산
        # 이전 결과 값을 항상 저장하고 있어야 함.
        cur = (cur + arr[i]) % mod

        # sort_p_i에서 현재 p_i가 들어갈 위치를 찾음
        pos = bisect.bisect(sort_p_i, cur)

        # sort_p_i의 모든 원소보다 p_i가 크다면 p==i가 됨. 
        # 그렇지 않고, sort_p_i 중간에 p_i가 들어가게 됨 -> p_i가 들어가게 되는 index 바로 다음 큰 수와의 차이를 계산
        d = 0 if pos == i else sort_p_i[pos]

        # d = 0인 경우, (cur+mod)%mod가 되는데, mod%mod = 0이므로, cur%mod가 됨.
        # 하지만 d = sort_p_i[pos]이면, pos는 cur 다음 큰 수의 index가 되고, d는 cur 바로 다음 큰 수를 나타냄.
        # bisect.bisect([1, 2, 5], 4) -> 2
        result = max(result, (cur - d + mod) % mod)

        # sort_p_i에 정렬된 상태를 유지하며 삽입.
        bisect.insort(sort_p_i, cur)

    return result