[문제풀이] Leetcode 53. Maximum Subarray 자바 풀이

👉 문제

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.

입출력 예시:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23

✨ 풀이

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

• 다이나믹 프로그래밍을 활용해서 가장 큰 부분합을 구하는 문제다. 따라서 인자로 주어진 nums와 같은 길이의 dp 배열을 만들고, 이것을 채워가며 가장 큰 부분합 max라는 수를 구한다.
• 현재 값인 dp[i]에 num 배열에 같은 인덱스 i에 있는 값을 넣어주는데, 이전 값이 0보다 크냐에 따라 더해주거나 더해주지 않는다.

max = 0;
max = Integer.MIN_VALUE;
max = dp[0];

• max 값을 처음에는 0으로 줬는데 [-1,-2] 같은 음수로만 이루어진 테스트 케이스에서 0이 반환되는 바람에 에러가 났다. 그래서 임의의 음수값을 주기 위해 Integer.MIN_VALUE로 수정했다.
  dp[0]=nums[0]라고 설정하고 배열을 인덱스 1부터 돌기 때문에 [-1, -2] 테스트 케이스에서 -1이 아닌 -2가 반환돼서 또 통과하지 못했다.
  결국 max=dp[0] 으로 바꿔주니 통과했다. 다이나믹 프로그래밍은 인덱스나 값 설정을 하나만 잘못해도 의도한 것과 다른 값이 돌아오니 신중할 필요가 있는 것 같다.