# Java solution for n non-overlapping intervals.

• 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;
}
}
``````

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