leetcode 53 java dp

/*
정수 배열 nums가 주어졌을 때, **가장 큰 합을 가지는 연속된 부분 배열(subarray)**을 찾아 그 합을 반환하세요.
*/

/*
dp[i] = max(dp[i-1]+nums[i], nums[i])
*/

class Solution {
    public int maxSubArray(int[] nums) {
        int result = -100001;
        int [] dp = new int[100000];
        Arrays.fill(dp, -100001);
        dp[0] = nums[0];
        for(int i=1; i<nums.length; i++) {
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
        }
        return Arrays.stream(dp).reduce((a,b) -> Math.max(a,b)).getAsInt();
    }
}

 

 

가장 큰 합을 찾는 문제이다.

 

예를들어 다음과 같은 입력이 있다고 가정하면

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

 

위와같이, 연속된 숫자중에서 4 -1 2 1 이 가장 큰 합을 가지고 그것을 출력하는 문제이다.

이와같은 속성으로 dp로 문제를 풀면된다.

앞의 갚이 뒤에 갚에 영향을 준다고 생각하면 된다.

 

점화식은 다음과 같다.

dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

 

만약 이전까지의 합(dp[i-1)과 현재값을 더한게 더 크다면 이것을 넣고, 아니면 자기자신을 넣으면된다.

자기자신을 넣는다는건 지금까지 탐색해왔던 연속된합보다 내가 더 크다는 것을 의미한다.

 

시간복잡도는 o(n) 이다.