Partition Array for Maximum Sum - LeetCode Daily Challenge

Problem Statement

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

Example 1

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84
Explanation: arr becomes [15,15,15,9,10,10,10]

Example 2

Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
Output: 83

Try here before watching the video.

Video Solution

Java Code

class Solution {

    private int solve(int[] arr, int k, int startIndex, int[] dp) {
        if(startIndex >= arr.length) return 0;

        if(dp[startIndex] != -1) return dp[startIndex];

        int currMax = 0, ans = 0;
        for(int i = startIndex; i < startIndex + k && i < arr.length; i++) {
            currMax = Math.max(currMax, arr[i]);
            int tempAns = (i - startIndex + 1) * currMax + solve(arr, k, i + 1, dp);
            ans = Math.max(ans, tempAns);
        }

        return dp[startIndex] = ans;
    }

    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, -1);
        return solve(arr, k, 0, dp);
    }
}

C++ Code

class Solution {
public:
    int solve(vector<int>& arr, int k, int startIndex, vector<int>& dp) {
        if (startIndex >= arr.size()) return 0;

        if (dp[startIndex] != -1) return dp[startIndex];

        int currMax = 0, ans = 0;
        for (int i = startIndex; i < startIndex + k && i < arr.size(); i++) {
            currMax = max(currMax, arr[i]);
            int tempAns = (i - startIndex + 1) * currMax + solve(arr, k, i + 1, dp);
            ans = max(ans, tempAns);
        }

        return dp[startIndex] = ans;
    }

    int maxSumAfterPartitioning(vector<int>& arr, int k) {
        vector<int> dp(arr.size(), -1);
        return solve(arr, k, 0, dp);
    }
};

Python Code

class Solution:
    def solve(self, arr, k, startIndex, dp):
        if startIndex >= len(arr):
            return 0

        if dp[startIndex] != -1:
            return dp[startIndex]

        currMax, ans = 0, 0
        for i in range(startIndex, startIndex + k if startIndex + k <= len(arr) else len(arr)):
            currMax = max(currMax, arr[i])
            tempAns = (i - startIndex + 1) * currMax + self.solve(arr, k, i + 1, dp)
            ans = max(ans, tempAns)

        dp[startIndex] = ans
        return ans

    def maxSumAfterPartitioning(self, arr, k):
        dp = [-1] * len(arr)
        return self.solve(arr, k, 0, dp)

Javascript Code

var maxSumAfterPartitioning = function(arr, k) {
    const solve = (startIndex, dp) => {
        if (startIndex >= arr.length) return 0;

        if (dp[startIndex] !== -1) return dp[startIndex];

        let currMax = 0, ans = 0;
        for (let i = startIndex; i < startIndex + k && i < arr.length; i++) {
            currMax = Math.max(currMax, arr[i]);
            const tempAns = (i - startIndex + 1) * currMax + solve(i + 1, dp);
            ans = Math.max(ans, tempAns);
        }

        dp[startIndex] = ans;
        return ans;
    };

    const dp = new Array(arr.length).fill(-1);
    return solve(0, dp);
};

Go Code

func solve(arr []int, k, startIndex int, dp []int) int {
	if startIndex >= len(arr) {
		return 0
	}

	if dp[startIndex] != -1 {
		return dp[startIndex]
	}

	currMax, ans := 0, 0
	for i := startIndex; i < startIndex+k && i < len(arr); i++ {
		currMax = max(currMax, arr[i])
		tempAns := (i - startIndex + 1) * currMax + solve(arr, k, i+1, dp)
		ans = max(ans, tempAns)
	}

	dp[startIndex] = ans
	return ans
}

func maxSumAfterPartitioning(arr []int, k int) int {
	dp := make([]int, len(arr))
	for i := range dp {
		dp[i] = -1
	}
	return solve(arr, k, 0, dp)
}

Complexity Analysis

Let N be the number of elements in the array, and K is the maximum length of a subarray.

• Time complexity: O(N * K). The time complexity for the recursion with memoization is equal to the number of times solve() is called times the average time of solve(). The number of calls to solve() is N because each non-memoized call will call solve() only once. Each memoized call will take O(1) time, while for the non-memoized call, we iterate over most K elements ahead of it. Hence, the total time complexity equals O(N * K).
• Space complexity: O(N). The result for each startIndex index will be stored in dp, and startIndex can have the values from 0 to N; thus, the space required is O(N). Also, the stack space needed for recursion is equal to the maximum number of active function calls which will be N, one for each index. Hence, the space complexity will equal O(N).