public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
if (nums == null || nums.length < 3 * k) {
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
// the subarray sum between nums[i...j] will be sum[j + 1] - sum[i], i and j both starts with 0
int[] leftIndex = new int[n];
int[] rightIndex = new int[n];
int curMaxSum = sum[k] - sum[0];
// Find the start point of max left sum subarray
// Since we have have calculated the sum of subarray(0, k - 1), we start at 1 here
for (int i = 1; i <= n - k; i++) {
if (sum[i + k] - sum[i] > curMaxSum) {
curMaxSum = sum[i + k] - sum[i];
leftIndex[i] = leftIndex[i - 1];
curMaxSum = sum[n] - sum[n - k];
rightIndex[n - k] = n - k;
// Find the start point of max right sum subarray
// Since we have have calculated the sum of subarray(n - k, n - 1), we start at n - k - 1 here
for (int i = n - k - 1; i >= 0; i--) {
// we use ">=" here because we try to make the answer lexicographically smaller.
// i.e. when there are subarray sum equal to the curMaxSum, we try to make the start point
if (sum[i + k] - sum[i] >= curMaxSum) {
curMaxSum = sum[i + k] - sum[i];
rightIndex[i] = rightIndex[i + 1];
// Find the start point of the max sum subarray in the middle
int maxSum = Integer.MIN_VALUE;
for (int i = k; i <= n - 2 * k; i++) {
int leftStart = leftIndex[i - k], rightStart = rightIndex[i + k];
curMaxSum = sum[leftStart + k] - sum[leftStart] + sum[rightStart + k] - sum[rightStart] + sum[i + k] - sum[i];
if (curMaxSum > maxSum) {