LeetCode 689. Maximum Sum of 3 Non-Overlapping Subarrays(JAVA)

출처 : https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/?envType=daily-question&envId=2024-12-28

 

#문제 

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.
Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

정수 배열nums와 정수k가 주어졌을 때, 합이 최대가 되는 길이k의 서로 겹치지 않는 세 개의 부분 배열을 찾아야 합니다.결과는 각 구간의 시작 위치(0부터 시작하는 인덱스)를 나타내는 리스트로 반환하세요.만약 답이 여러 개인 경우,사전순으로 가장 작은답을 반환하세요.

 

접근 : DP(배낭문제 응용)

1) 길이 k인 구간별 합을 미리 계산하여 sum 배열에 저장

2) 각 구간에서 선택 가능한 최대 합과 해당 구간의 인덱스를 저장 (dpMaxSum, dpAddedIndex)

3) dpAddedIndex  테이블을 통해  저장된 인덱스를 역추적하여 결과를 반환

public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    int n = nums.length;
    //각 자리에서 k길이만큼의 합을 구한다.
    int[] sum = new int[n-k+1];
    for(int i = 0 ;i<k;i++){
        sum[0] += nums[i];
    }
    for(int i = 1; i <= n-k;i++){
        sum[i] = sum[i-1] +nums[i+k-1]-nums[i-1];
    }

    //sum에서 범위가 겹치지않도록 n개의 값을 골랐을때 최대 값
    //dpMaxSum[i][j] = k ==> i까지의 sum에서 j개의 값을 골랐을때의 최댓값
    int[][] dpMaxSum = new int[n-k+1][4];
    //dpMaxSum의 최댓값이 갱신됐을때 sum에서 추가한 자리
    //dpAddedIndex[i][j] = k ==> i까지의 sum에서 j개의 값을 골랐을때 최댓값을 가지도록하는 가장 최근에 추가된 인덱스
    //즉, 0<= k <= i
    int[][] dpAddedIndex = new int[n-k+1][4];
    for(int i = 0;i<n-k+1;i++){
        for (int j = 1 ;j < 4 ;j++){
            if(i >= k){
                if(dpMaxSum[i-1][j] >= sum[i] + dpMaxSum[i-k][j-1]){
                    dpMaxSum[i][j] = dpMaxSum[i-1][j];
                    dpAddedIndex[i][j] = dpAddedIndex[i-1][j];
                }else{
                    dpMaxSum[i][j] = sum[i] + dpMaxSum[i-k][j-1];
                    dpAddedIndex[i][j] = i;
                }
            }else{
                if(i>0){
                    if(dpMaxSum[i-1][j] >= sum[i]){
                        dpMaxSum[i][j] = dpMaxSum[i-1][j];
                        dpAddedIndex[i][j] = dpAddedIndex[i-1][j];
                    }else{
                        dpMaxSum[i][j] = sum[i];
                        dpAddedIndex[i][j] = i;
                    }
                }else{
                    dpMaxSum[i][j] = sum[i];
                    dpAddedIndex[i][j] = i;
                }


            }
        }
    }

    //저장된 인덱스로 답 역추적
    int[] result = new int[3];
    int current = n - k;
    for (int j = 3; j >= 1; j--) {
        result[j - 1] = dpAddedIndex[current][j];
        current = result[j - 1] - k;
    }
    return result;
}