We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition Array for Maximum Sum

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be approached using dynamic programming to optimize the partitioning process.
  • For each index in the array, consider all possible partitions ending at that index, up to length k.
  • The maximum value of each partition can be computed to build the sum iteratively.
  • The goal is to keep track of the maximum sum at each position while considering previous partitions.

Space and Time Complexity

Time Complexity: O(n * k) where n is the length of the array and k is the maximum partition length. Space Complexity: O(n) for the dynamic programming array to store results.

Solution

The solution employs dynamic programming. We define a DP array where dp[i] represents the maximum sum obtainable for the subarray arr[0...i]. For each position i, we consider all possible previous partitions of length up to k, calculate the maximum value in the current partition, and update the DP array accordingly. This allows us to build the maximum achievable sum incrementally based on previous results.

Code Solutions

def maxSumAfterPartitioning(arr, k):
    n = len(arr)
    dp = [0] * n
    
    for i in range(n):
        max_value = 0
        for j in range(1, min(k, i + 1) + 1):
            max_value = max(max_value, arr[i - j + 1])
            if i - j >= 0:
                dp[i] = max(dp[i], dp[i - j] + max_value * j)
            else:
                dp[i] = max(dp[i], max_value * j)
    
    return dp[-1]
← Back to All Questions