Java solution for n non-overlapping intervals.


  • 0
    Y

    Iteratively find the max interval in each round. Then search backward in the dp array to find which indexes made up the maximum sum intervals.

    class Solution {
        public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
            return maxSumOfThreeSubarrays(nums, k, 3);
        }
        
        public int[] maxSumOfThreeSubarrays(int[] nums, int k, int n) {
            int[][] dp = new int[n + 1][nums.length + 1];
            int[][] index = new int[n + 1][nums.length + 1];
            int tot = 0;
            // prefix sum
            int[] sum = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                sum[i + 1] = nums[i] + sum[i];
            }
            
            for (int i = 1; i <= n; i++) {
                for (int j = k - 1; j < nums.length; j++) {
                    int tmpMax = sum[j + 1] - sum[j - k + 1] + dp[i - 1][j - k + 1];
                    if (tmpMax > dp[i][j]) {
                        dp[i][j + 1] = tmpMax;
                        index[i][j + 1] = j - k + 1;
                    } else {
                        dp[i][j + 1] = dp[i][j];
                        index[i][j + 1] = index[i][j];
                    }
                }
            }
            
            int[] ret = new int[n];
            int prev = nums.length;
            for (int i = n; i > 0; i--) {
                ret[i - 1] = index[i][prev];
                prev = ret[i - 1];
            }
            
            return ret;
        }
    }
    

Log in to reply
 

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