Java DP solution, one pass


  • 0

    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];
        }
    

Log in to reply
 

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