3 개의 겹치지 않는 하위 배열의 최대 합

난이도 하드
자주 묻는 질문 Facebook
배열 동적 프로그래밍조회수 23

3 개의 겹치지 않는 부분 배열 문제의 최대 합에서 우리는 정렬 nums의 양의 정수, 최대 합을 가진 길이 k의 겹치지 않는 부분 배열 XNUMX 개를 찾아 시작 인덱스를 반환합니다.

입력:
nums [] = {1, 2, 1, 2, 6, 7, 5, 1}
k = 2
출력:
{0, 3, 5}

3 개의 겹치지 않는 부분 배열의 최대 합에 대한 알고리즘

아이디어는 모든 k 길이 연속 하위 배열의 합계를 저장하는 합계 배열을 만드는 것입니다. 인덱스 i의 경우, 여기서 얻은 최대 합은 sum [i] + 인덱스 0에서 (i -k)까지의 합의 최대 값 + 인덱스 (i + k)에서 합의 길이까지의 합의 최대 값입니다.

왼쪽과 오른쪽 배열을 2 개 더 만듭니다. 여기서 left는 해당 인덱스까지 길이 k의 연속 배열의 최대 합계 인덱스를 저장하고 right도 동일하지만 끝부터 시작합니다.

인덱스 k에서 인덱스 (합의 길이 – k)까지 배열 합계를 탐색합니다. 각 인덱스 i에 대해 여기서 얻은 최대 합계는 다음과 같습니다. 합계 [i] + 합계 [왼쪽 [i – k]] + 합계 [오른쪽 [i + k]].
가능한 모든 합계에 대해 최대 합계와 해당 인덱스를 찾으십시오.

겹치지 않는 3 개의 하위 배열의 최대 합에 대한 설명

위의 예에서 배열을 고려하십시오.
nums [] = {1, 2, 1, 2, 6, 7, 5, 1} 및 k = 2

nums 배열의 경우 길이가 2 인 연속 하위 배열의 가능한 모든 합계를 저장하는 합계 배열을 만듭니다.
합계 [] = {3, 3, 3, 8, 13, 12, 6}

알고리즘에 설명 된대로 왼쪽 및 오른쪽 배열 만들기
왼쪽 [] = {0, 0, 0, 3, 4, 4, 4}
오른쪽 [] = {4, 4, 4, 4, 4, 5, 6}

인덱스 2부터 인덱스 4까지 합계 배열을 순회합니다.

  • i = 2, 합계 [i] = 3
    인덱스 2에서 얻은 합계 = 3 + (sum [left [2 – 2]]) + (sum [right [2 + 2]]) = 19
  • i = 3, 합계 [i] = 8
    인덱스 3에서 얻은 합계 = 8 + (sum [left [3 – 2]]) + (sum [right [3 + 2]]) = 23
  • i = 4, 합계 [i] = 13
    인덱스 4에서 얻은 합계 = 13 + (sum [left [4 – 2]]) + (sum [right [4 + 2]]) = 22

3 개의 겹치지 않는 하위 배열의 최대 합

얻은 최대 합계 = 23이고 시작 인덱스는 {0, 3, 5}입니다.

겹치지 않는 3 개의 하위 배열의 최대 합계에 대한 JAVA 코드

public class MaximumSumOfThreeNonOverlappingIntervals {
    private static int[] findInicies(int[] nums, int k) {
        int n = nums.length;

        // build sum array that stores the sum of all k length continuous subarrays
        int sum[] = new int[n - k + 1];
        int currSum = 0;
        for (int i = 0; i < k; i++) {
            currSum += nums[i];
        }

        sum[0] = currSum;

        for (int i = k;i < n; i++) {
            currSum -= nums[i - k];
            currSum += nums[i];
            sum[i - k + 1] = currSum;
        }

        // Create left array that stores the index of maximum sum of contiguous array of length k upto that index
        int left[] = new int[sum.length];
        int best = 0;
        for (int i = 0; i < sum.length; i++) {
            if (sum[i] > sum[best]) {
                best = i;
            }
            left[i] = best;
        }

        best = sum.length - 1;
        // Create right array that stores the index of maximum sum of contiguous array of length k upto that index
        // starting from end
        int right[] = new int[sum.length];
        for (int i = sum.length - 1; i >= 0; i--) {
            if (sum[i] >= sum[best]) {
                best = i;
            }
            right[i] = best;
        }

        // Initialise ans array as -1
        int ans[] = new int[] {-1, -1, -1};
        // Traverse in sum array from index k to (sum length - k)
        for (int i = k; i < sum.length - k; i++) {
            // Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
            int l = left[i - k];
            int r = right[i + k];
            if (ans[0] == -1 ||
                    (sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
                // Update the indices if the max sum is greater than the actual max sum
                ans[0] = l;
                ans[1] = i;
                ans[2] = r;
            }
        }

        // return ans array
        return ans;
    }

    public static void main(String[] args) {
        // Example
        int nums[] = new int[] {1,2,1,2,6,7,5,1};
        int k = 2;

        int indices[] = findInicies(nums, k);
        for (int i = 0; i < 3; i++)
            System.out.print(indices[i] + " ");
        System.out.println();
    }
}

겹치지 않는 3 개의 하위 배열의 최대 합계에 대한 C ++ 코드

#include <iostream>
#include <vector>
using namespace std;

void findIndices(int *nums, int k, int n, vector<int> &ans) {
    // build sum array that stores the sum of all k length continuous subarrays
    int sum[n- k + 1];
    int currSum = 0;
    for (int i = 0; i < k; i++) {
        currSum += nums[i];
    }

    sum[0] = currSum;

     for (int i = k;i < n; i++) {
        currSum -= nums[i - k];
        currSum += nums[i];
        sum[i - k + 1] = currSum;
    }
    
    // Create left array that stores the index of maximum sum of contiguous array of length k upto that index
    int left[n - k + 1];
    int best = 0;
    for (int i = 0; i < n - k + 1; i++) {
        if (sum[i] > sum[best]) {
            best = i;
        }
        left[i] = best;
    }
    
    best = n - k;
    // Create right array that stores the index of maximum sum of contiguous array of length k upto that index
    // starting from end
    int right[n - k + 1];
    for (int i = n - k; i >= 0; i--) {
        if (sum[i] >= sum[best]) {
            best = i;
        } 
        right[i] = best;
    }
    
    // Initialise ans array as -1
    ans.push_back(-1);
    ans.push_back(-1);
    ans.push_back(-1);
    // Traverse in sum array from index k to (sum length - k)
    for (int i = k; i < (n - k + 1 - k); i++) {
        // Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
        int l = left[i - k];
        int r = right[i + k];
        if (ans[0] == -1 ||
                (sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
            // Update the indices if the max sum is greater than the actual max sum
            ans[0] = l;
            ans[1] = i;
            ans[2] = r;
        }
    }
}

int main() {
    int nums[] = {1,2,1,2,6,7,5,1};
    int k = 2;
    int n = sizeof(nums) / sizeof(nums[0]);
    
    vector<int> ans;
    findIndices(nums, k, n, ans);
    for (int i = 0; i < ans.size(); i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
    
    return 0;
}
0 3 5

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (N)

여기서 n은 주어진 배열에있는 요소의 수입니다.

참조

Translate »