# Java DP solution, one pass

• It is easier to calculate value only. However, to record the position information, I did some tricks to memorize the optimal positions for each location in the array.

``````    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] res = new int[3];
if (nums == null || k <= 0 || nums.length < 3 * k) {
return res;
}
int n = nums.length;
int[] sums = new int[n + 1];
for (int i = 1; i <= n; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}

int[][] dp = new int[4][n + 1];
int[][][] pos = new int[4][n + 1][3];

for (int i = 1; i <= 3; i++) {
for (int j = n - k * i; j >= 0; j--) {
if (sums[j + k] - sums[j] + dp[i - 1][j + k] >= dp[i][j + 1]) {
dp[i][j] = sums[j + k] - sums[j] + dp[i - 1][j + k];
pos[i][j][3 - i] = j;
for (int m = 3 - i + 1; m < 3; m++) {
pos[i][j][m] = pos[i - 1][j + k][m];
}
} else {
dp[i][j] = dp[i][j + 1];
pos[i][j][3 - i] = j;
for (int m = 3 - i; m < 3; m++) {
pos[i][j][m] = pos[i][j + 1][m];
}
}
}
}
return pos[3][0];
}
``````

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