[LeetCode] 53. Maximum Subarray - 동적계획법(DP, Dynamic Programming) JAVA

https://leetcode.com/problems/maximum-subarray/description/

코드설명

동적계획법(DP, Dynamic Programming) 을 활용합니다.

 

dp[i] = [0..i] 에서 최대부분배열의 합입니다.

중요한점은, 만약 이전 부분배열 DP[i-1]이 음수라면, 현재값을 더하면 반드시 숫자가 작아집니다. 그러므로 최대값을 계속해서 갱신해나갑니다.

코드

class Solution {
    public int maxSubArray(int[] nums) {
        int answer = -(int) Math.pow(10, 4);
        int[] dp = new int[nums.length];

        for(int i=0; i<nums.length; i++){
            if(i == 0) {
                answer = nums[0];
                dp[i] = nums[0];
                continue;
            }

            if(dp[i -1] > 0) dp[i] = dp[i-1] + nums[i];
            else dp[i] = nums[i];

            answer = Math.max(answer, dp[i]);
        }

        return answer;
    }
}

 

 

처음에 분할정복으로 풀어보려고 한 코드입니다.. 하지만 실패했습니다.

class Solution {
    int[] Nums;
    public int maxSubArray(int[] nums) {
        int MAX = nums[0];
        int now = nums[0];
        int temp = 0;
        for(int i=1; i<nums.length; i++){
            temp = nums[i];
            if(nums[i] > 0){
                MAX = Math.max(nums[i], MAX + nums[i]);
            }
            else if(nums[i] < 0){
                temp = temp
            }
        }
        return dq(0, Nums.length - 1);
    }
}

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

//     int dq(int left, int right){
//         if(left == right) return Nums[left];

//         int mid = (left + right) / 2;
//         int num1 = dq(left, mid);
//         int num2 = dq(mid + 1, right);

//         int num3 = 0;
//         for(int i=left; i<=right; i++){
//             num3 += Nums[i];
//         }

//         return Math.max(num1, Math.max(num2, num3));
//     }
// }