Java DP Generic Solution for M subarrays


  • 0
    K
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int n = nums.length;
        int m = 3;
        int[] sums = new int[n+1];
        int[][] max = new int[n+1][m+1];
        int[][] indices = new int[n+1][m+1];
        for (int i = 1; i <= n; i++)
            sums[i] = sums[i-1]+nums[i-1];
        for (int i = 1; i <= m; i++) {
            for (int j = i*k; j <= n; j++) {
                if (max[j-k][i-1]+sums[j]-sums[j-k] > max[j-1][i]) {
                    indices[j][i] = j-k;
                    max[j][i] = max[j-k][i-1]+sums[j]-sums[j-k];
                } else {
                    max[j][i] = max[j-1][i];
                    indices[j][i] = indices[j-1][i];
                }
            }
        }
        int[] ret = new int[m];
        ret[m-1] = indices[n][m];
        for (int i = m-2; i >= 0; i--)
            ret[i] = indices[ret[i+1]][i+1];
        return ret;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.