3个非重叠子阵列的最大和


难度级别
经常问 Facebook
排列 动态编程

在3个非重叠子数组问题的总和中,我们给出了一个 排列 数量的正整数,找到三个具有最大和的长度为k的非重叠子数组,并返回它们的起始索引。

使用案列

输入:
nums [] = {1}
k = 2
输出:
{0,3,5}

3个非重叠子阵列的最大和算法

这个想法是建立一个求和数组,该数组存储所有k个长度连续的子数组的和。 对于索引i,从索引i获得的最大和为sum [i] +从索引0到(i -k)的和的最大值+从索引(i + k)到和的长度的和的最大值。

左右再创建2个数组,其中,left存储长度为k的连续数组的最大和的索引,直到该索引为止; right也存储相同数组,但从末尾开始。

从索引k开始遍历数组总和到索引(总和– k的长度),对于每个索引i,从数组中获得的最大总和为 sum [i] + sum [left [i – k]] + sum [right [i + k]].
对于所有可能的总和,找到最大总和及其对应的索引。

3个非重叠子阵列的最大和的说明

考虑上面示例中的数组,
nums [] = {1},k = 2

对于nums数组,构建sum数组可存储长度为2的连续子数组的所有可能的和。
sum [] = {3,3,3,8,13,12,6}

如算法中所述,左右创建数组
left [] = {0,0,0,3,4,4,4}
right [] = {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}

JAVA代码,用于3个非重叠子数组的最大和

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是给定数组中存在的元素数。

參考資料