May LeetCoding Challenge[Day15] - Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 Input이 주어질 때, 최대의 Input이 순환하는 배열이라고 생각하고, 부분합을 구하는 문제이다. 

 - 부분합은 [5, -3, 5] 라면, 5 + (-3) + 5와 같이 배열의 원소들의 합을 말한다.

 - 순환하는 배열은 [5), -3, (5]와 같이 (5,5)가 배열의 최대합이 될 수 있다.

 - 배열 안에서 가장 큰 값이나 가장 작은 값을 구하기 위해서는 Kadane 알고리즘을 사용해야 한다. 

 

2. 알고리즘 작성 중, 어려운 점

 - 부분으 배열합을 어떻게 구할 수 있을까?

 - 순환 구조를 어떻게 해결할 수 있을까?

 - Kadane 알고리즘은 무엇인가?

 

3. Kadane 알고리즘 공부하기

 

4. 다른 사람의 강의를 참고하자

 

https://www.youtube.com/watch?v=s1CYAnJwf50

5. 다른 사람이 작성한 알고리즘을 보고, 공부한 내용

 

 

6. 이해한 점을 바탕으로 로직 작성하기

class Solution {
    public int maxSubarraySumCircular(int[] A) {
        int cur1 = 0;
        int cur2 = 0;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0; i<A.length; i++){
            cur1 += A[i];
            max = Math.max(max, cur1);
            cur1 = Math.max(0, cur1);
            
            cur2 += A[i];
            min = Math.min(min, cur2);
            cur2 = Math.min(0, cur2);
            
            sum += A[i];
        }
        
        return max < 0 ? max : Math.max(max , sum-min);
    }
}

 

7. 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3330/

Explore - LeetCode