# 1043. Partition Array for Maximum Sum

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int maxSumAfterPartitioning(vector& arr, int k) { const int n = arr.size(); vector dp(n + 1); for (int i = 1; i <= n; ++i) { int maxi = INT_MIN; for (int j = 1; j <= min(i, k); ++j) { maxi = max(maxi, arr[i - j]); dp[i] = max(dp[i], dp[i - j] + maxi * j); } } return dp[n]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int maxSumAfterPartitioning(int[] arr, int k) { final int n = arr.length; int[] dp = new int[n + 1]; for (int i = 1; i <= n; ++i) { int max = Integer.MIN_VALUE; for (int j = 1; j <= Math.max(i, k); ++j) { max = Math.max(max, arr[i - j]); dp[i] = Math.max(dp[i], dp[i - j] + max * j); } } return dp[n]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int: n = len(arr) dp = [0] * (n + 1) for i in range(1, n + 1): maxi = -math.inf for j in range(1, min(i, k) + 1): maxi = max(maxi, arr[i - j]) dp[i] = max(dp[i], dp[i - j] + maxi * j) return dp[n]