[Leet Code] Maximum Subarray (Java)

Leet Code Maximum Subarray 문제

Given an integer array nums, find the
subarray
with the largest sum, and return its sum.

DP를 활용한 풀이

각 요소(element)마다 2가지의 옵션을 고려한다.
1. 지금까지의 sum에 현재 요소를 더한다
2. 지금까지의 sum 초기화하고 현재 요소부터 다시 sum을 구한다.

int 리스트와 동일한 길이의 DP 리스트를 만들고, 2가지 중 sum이 큰 값을 DP 리스트에 저장하면 각 인덱스까지의 subarray에서 만들 수 있는 최댓이 각 인덱스에 저장할 수 있다. DP 리스트에서의 최댓값이 답이다.

하지만, 굳이 리스트가 없어도 MaxSum을 저장할 변수 하나만 있어도 답을 구하는 데에는 문제가 없다. 지금까지의 최대합이 음수값이라면, 최대합을 0으로 초기화 즉, 현재 요소부터 다시 최대합을 구하는 것이 적절하다

지금까지의 최대합이 음수값이라면 지금까지 최대합을 현재요소부터 다시 측정하고 전체 최댓값을 지속적으로 업데이트 해야 한다.

class Solution {
    public int maxSubArray(int[] nums) {
        int curSum = nums[0];
        int maxValue = nums[0];
        for (int i = 1; i < nums.length; i++)
        {
            if (0 < curSum)
            {
                curSum += nums[i];
            }
            else
            {
                curSum = nums[i];
            }
            maxValue = Math.max(curSum, maxValue);
        }
        return maxValue;
    }
}