Medium - K-Concatenation Maximum Sum

https://leetcode.com/problems/k-concatenation-maximum-sum/description/

K-Concatenation Maximum Sum - LeetCode

문제 설명

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 109 + 7.

Constraints:

• 1 <= arr.length <= 105
• 1 <= k <= 105
• -104 <= arr[i] <= 104

예시

Input: arr = [1,2], k = 3
Output: 9

Input: arr = [1,-2,1], k = 5
Output: 2

Input: arr = [-1,-2], k = 7
Output: 0

풀이

class Solution:
    def kConcatenationMaxSum(self, arr: List[int], k: int) -> int:
        MOD = 10 ** 9 + 7
        univ_max = -float('inf')
        cur = 0
        start, end, s = 0, 0, 0
        size = len(arr)
        arr_sum = sum(arr)

        if k != 1:
            arr.extend(arr)

        for i in range(len(arr)):
            cur += arr[i]

            if univ_max < cur:
                univ_max = cur
                start = s
                end = i
            
            if cur < 0:
                cur = 0
                s = i + 1

        if univ_max < 0:
            return 0

        if k == 1:
            return univ_max
            
        if end - start + 1 < size: # no loop
            return univ_max
        
        return (univ_max + (k - 2) * arr_sum) % MOD

코딩 테스트 단골 문제인 maximum sub-array sum 문제다.

하지만 k번 반복하고 sub-array sum이 0보다 작을 경우 0을 제출한다는 차이점이 있다.

주어진 array를 k가 1이면 한 번, k가 2 이상일 때 두 번 돌면서 maximum sub-array sum을 구하고, maximum sub-array의 시작과 끝 인덱스를 사용해서 루프가 있는지 확인한다.