문제

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

제한사항

• 1 $\leq$ nums.length $\leq$ $10^5$
• $-10^4$ $\leq$ nums[i] $\leq$ $10^4$

접근 1

처음엔 투 포인터 방식으로 접근했어요.

1. left = 0, right = nums.length - 1부터 시작해요.
2. max {left ~ right까지 합, left - 1 ~ right까지 합, left ~ right - 1까지 합}으로 해서 재귀적으로 접근해요.
3. 재귀 함수는 left $\geq$right까지만 수행해요.

물론, 이 방식으로 접근하면 $O(n^2)$ 시간 복잡도를 가져 $10^5$길이의 배열에선 당여언~히 시간 초과가 뜹니다 그래요, 제한사항 똑바로 안봤어요.

답안

public class Solution {
	public int maxSubArray(int[] nums) {
        return getValue(nums, 0, nums.length - 1);
    }

    private int getValue(int[] nums, int left, int right){
        if(left >= right)
            return nums[left];

        return Math.max(getSum(nums, left, right), Math.max(getValue(nums, left + 1, right), getValue(nums, left, right - 1)));
    }

    private int getSum(int[] nums, int left, int right){
        int sum = 0;
        for(int i = left; i <= right; ++i){
            sum += nums[i];
        }
        return sum;
    }
}

접근 2

당여언히 안되는 걸 깨닫고 다른 방식으로 접근했어요. 그리고 Dynamic Programming으로 해결했어요.

1. i = 1부터해서 dp[i] = max{dp[i-1] + nums[i], nums[i]}로 dp 배열을 초기화해요.
2. 그리고 초기화할 때마다 answer 변수와 비교해서 큰 값을 answer에 초기화 해줍니다.

해당 문제는 연속적인 부분배열의 합을 반환하는 문제니까 다음 값을 더하거나 아님 혼자 놀거나, 즉, 부분 배열을 이룰 것이냐, 단일 원소부터 다시 전개할 것이냐라는 분기점으로 초기화를 수행하는 거에요.

nums : | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |

해당 예제를 위 방식대로 dp를 전개하면,

dp : | -2 | 1 | -2 | 4 | 3 | 5 | 6 | 1 | 5 |

이렇게 dp 배열의 원소는 해당 위치가 마지막일 경우에 대한 최대값을 초기화하므로 answer 값을 dp 배열 초기화 동시에 비교해서 초기화해주면 되요.

간만에 다른 사람 풀이 안보고도 최적 속도로 문제를 풀어서 기분이 좀 좋네요 ㅎㅎ. 자기전에 아쉬운 맘에 Easy 모드를 골라 풀었는데 뿌듯하네요.

답안

class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        
        int answer = dp[0];
        for(int i = 1; i < nums.length; ++i){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            answer = Math.max(answer, dp[i]);
        }
        return answer;
    }
}