[Leetcode(릿코드)] 53. Maximum Subarray (Easy)

leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

---

문제

subarray의 합이 최대일 때, 그 값을 출력하는 문제이다

 

해결

dp배열을 이용해 풀었다 (시간복잡도 : O(N))

dp 배열을 만들고, dp 값을 계산하면서 max 값을 update
ex) nums : -2 1 -3 4 -1 2 1 -5 4
     dp : -2 1 -2 4 3 5 6 1 5
dp는 해당 인덱스까지의 서브 어레이의 합을 계산 & 이전 dp값이 -이면 현재 num[i]로 새로 업데이트 한다

public int maxSubArray(int[] nums) {
    int[] dp = new int[nums.length];
    int max = nums[0];
    dp[0] = nums[0];
    for (int i=1; i<nums.length; i++) {
        if (dp[i-1] < 0) {
            dp[i] = nums[i];
        } else {
            dp[i] = nums[i] + dp[i-1];
        }
        max = dp[i] > max ? dp[i] : max;
    }

    return max;
}