[LeetCode] Maximun Subarray

Maximun Subarray

숫자가 쓰여져 있는 배열에서 가장 큰 서브 배열을 찾아서 합을 반환하라.

첫 생각

투포인터? 그치만, 음수가 있고, 그 음수를 지나치는 방법이 도저히 떠오르지가 않는다.
설사, 구현하더라고 비효율적이라고 판단했다.

결국은 DP

import java.util.*;

class Solution {
    public int maxSubArray(int[] nums) {
        List<Integer> sums = new ArrayList<>(List.of(nums[0]));

        for(int i=1; i<nums.length; i++) {
            sums.add(nums[i] + (sums.get(i-1) > 0 ? sums.get(i-1) : 0));
        }

        return Collections.max(sums);    
    }
}

이것도 충분히 좋다고 생각하지만 좀 더 최적화 된 방법이 있다.

굳이 sums라는 변수를 사용해야 할까?

import java.util.*;

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = 0;
        int res = Integer.MIN_VALUE;

        for(int num : nums) {
            // 누적 값과 현재 값을 비교하여 항상 최대를 찾자
            currentSum = Math.max(num, currentSum + num);
            res = Math.max(res, currentSum);
        }

		return res;    
    }
}

이런 식으로도 풀이가 가능하다는 걸 배웠다.

앞으로 제대로 사용해보자!