You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.
Note that the partition must use every integer in nums, and that the score is not necessarily an integer.
Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.
Example 1:
Input: nums = [9,1,2,3,9], k = 3 Output: 20.00000 Explanation: The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20. We could have also partitioned nums into [9, 1], [2], [3, 9], for example. That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
Example 2:
Input: nums = [1,2,3,4,5,6,7], k = 4 Output: 20.50000
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 1041 <= k <= nums.lengthThis approach utilizes dynamic programming combined with prefix sums to efficiently calculate the sum of subarray averages when partitioned optimally. The prefix sum array allows for quick computation of subarray sums, and dynamic programming is used to build the optimal solution up to k partitions.
First, compute prefix sums for the array, then utilize dynamic programming to calculate the maximum sum of averages for each possible partition using the prefix sums. The dp array stores the maximum score achievable for each subarray starting at index i using up to m partitions.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k), where n is the length of the array, and k is the number of partitions.
Space Complexity: O(n * k) due to the dp table.
This approach uses recursion with memoization to solve for the maximum sum of averages by exploring all possible partition strategies and storing computed results for reuse. This avoids redundant computations and optimizes performance compared to plain recursion.
This C implementation defines a solve function that handles partitioning recursively, memoizing previously calculated scores to prevent redundant computation. This function checks scores for partitions from index i with m partitions left.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * k) as each subproblem is solved once.
Space Complexity: O(n * k) for memoization table.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming with Prefix Sums | Time Complexity: O(n^2 * k), where n is the length of the array, and k is the number of partitions. |
| Approach 2: Recursive with Memoization | Time Complexity: O(n^2 * k) as each subproblem is solved once. |
Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python • NeetCode • 605,117 views views
Watch 9 more video solutions →Practice Largest Sum of Averages with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor