[python3/파이썬/자바] leetcode 53. Maximum Subarray

문제

가장 최대가 되는 연속 부분합 구하기 

https://leetcode.com/problems/maximum-subarray/description/

Maximum Subarray - LeetCode

---

풀이

연속 부분합 이라 함은 [ 0 .. n ] 구간의 연속 적인 누적합을 말한다.

[ a .. b ] 구간의 합이 최대가 되는 누적합인데 

PointOfView  : 모든 배열이 음수도 가능하다.  이를테면 [-1,-2] 

즉 양수만 있는 것이 아니다. 그러면 단순히 naive 하게 , O(n^2) 로 2차 순회로 최댓값을 구하는 것을 떠올릴 수 있다. 

최적화를 해 보자면, 모든 구간의 합을 더할 필요는 없다. 

즉 

[ 1 , 2, -4, -5, 2 , -1, 5 ] 

다음과 같은 배열이 있을때, [2, -1, 5 ] 구간의 합이 제일 크다. 여기서 2차 순회는 nums[i] 가 1일때. 한번쫙 2일때 한번쫙.. -4는 안되고.... 하는 것보다 . 현재까지 누적합 Sum  변수를 만들어서 O(N) 으로 구해보자. 

 

알고리즘은 다음과 같다.

1. 현재까지 누적합 Sum. 
2. Sum + nextNum  > 0 이면 max값 업데이트 해주면서 계속 더한다. 
3. Sum + nuxtNum <= 0 이면 Sum = 0 으로 초기화를 해준다. 
4. 배열에 양수가 하나도 없으면 예외처리를 한다. 

이런식으로 하면 답을 도출 할 수있다.

---

코드

자바

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        boolean hasPlus = nums[0] > 0;
        int minusM = hasPlus ? 0 : nums[0];
        
        for(int x : nums){
            if(sum < 0) sum = 0;
            if(sum + x > 0 ){
                sum += x;
                max = Math.max(max, sum);
            }else{
                sum = 0 ;
            }

            if (x > 0){
                hasPlus = true;
            }else{
                minusM = Math.max(minusM, x);
            }
        }
        return hasPlus ? max : minusM;
    }
}

파이썬3

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        s = nums[0]
        m = nums[0]
        there_is_plus = nums[0] > 0

        minus_min = 0 if there_is_plus else nums[0]

        for i in range(1,len(nums)):
            if s < 0 : s =0 
            s = s+nums[i] if s+nums[i] > 0 else 0
            if nums[i] > 0 : 
                there_is_plus = True
            else :
                minus_min = max(minus_min, nums[i])
            m = max(m,s)
        if there_is_plus: return m
        else : return minus_min