Java general solution works for N subarrays.


  • 0
    L
    class Solution {
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            int[][] dp = new int[4][nums.length+1];
            int[][] loc = new int[4][nums.length+1];
            int[] sum = new int[nums.length + 1];
            for(int i = 1; i <= nums.length; i++) {
                sum[i] = sum[i-1] + nums[i-1];
            }
            for(int i = 1; i < 4; i++) {
                for(int j = k; j <= nums.length; j++) {
                    int cur = sum[j] - sum[j-k] + dp[i-1][j-k];
                    if(dp[i][j-1] < cur) {
                        dp[i][j] = cur;
                        loc[i][j] = j-k;
                    }else {
                        dp[i][j] = dp[i][j-1];
                        loc[i][j] = loc[i-1][j];
                    }
                }
            }
            int[] result = new int[3];
            int i = 3;
            int j = nums.length;
            int c = 3;
            while(c > 0) {
                if(loc[i][j] == j-k) {
                    result[--c] = j-k;
                    i = i-1;
                    j = j-k;
                }
                else {
                    j = j-1;
                }
            }
            return result;
        }
        
    }
    

Log in to reply
 

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