Max sum after partitioning

XXX. Max Sum After Partitioning

Dynamic Programming

Array

Problem Statement:

Given an integer array A, partition it into contiguous subarrays of length at most K. After partitioning, replace each subarray by the maximum element from that subarray. The score of the array is the sum of the replaced subarray values. Return the maximum score that can be achieved.

Algorithm:

The problem can be solved using dynamic programming:

1. Define a DP array dp, where dp[i] represents the maximum sum achievable for the first i elements of the array.
2. Iterate through the array and consider all possible partitions ending at the current index with length up to K.
   • For each partition, calculate the maximum element in the partition.
   • Update dp[i] as the maximum value of the current sum plus the sum of the partition.
3. Continue until the entire array is processed, and return dp[N], where N is the length of the array.

Complexity:

Time Complexity: O(N * K), where N is the length of the array and K is the maximum partition size.
Space Complexity: O(N), for the dp array.

Java Implementation:

public class Solution {
    public int maxSumAfterPartitioning(int[] A, int K) {
        int N = A.length;
        int[] dp = new int[N + 1]; // dp[i] represents the max sum for the first i elements

        for (int i = 1; i <= N; ++i) {
            int curMax = 0, best = 0;

            // Consider partitions of length up to K ending at the current index
            for (int k = 1; k <= K && i - k >= 0; ++k) {
                curMax = Math.max(curMax, A[i - k]); // Maximum element in the current partition
                best = Math.max(best, dp[i - k] + curMax * k); // Update the best sum for dp[i]
            }

            dp[i] = best; // Store the result for the first i elements
        }

        return dp[N]; // Maximum sum for the entire array
    }
}