LeetCode: Largest Sum of Averages

Posted on April 8, 2018July 26, 2020 by braindenny

Largest Sum of Averages

Similar Problems:

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

Example:

Input: 
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation: 
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Note:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
Answers within 10^-6 of the correct answer will be accepted as correct.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: From right to left. Space: n

// https://code.dennyzhang.com/largest-sum-of-averages
// Basic Ideas: DP
//
// Initial idea:
//  dp(i, k): nums[0...i], k
//
//    dp(j, k-1) + nums[j+1...i]
//
//    base condition: dp(i, 1)
//
// Improvement: From right to left
//    dp(i, k): nums[i...len(A)-1], k
//
//       nums[i...j-1], dp(j, k-1)
//
// Complexity: Time O(K*n*n), Space O(n)
func max(x, y float64)float64 {
    if x>y {
        return x
    } else {
        return y
    }
}

func largestSumOfAverages(A []int, K int) float64 {
    presums := make([]float64, len(A)+1)
    for i, v := range A{
        presums[i+1] = presums[i] + float64(v)
    }
    dp := make([]float64, len(A))

    // base condition: with one group
    for i, _ := range dp {
        dp[i] = (presums[len(A)]-presums[i])/float64(len(A)-i)
    }

    // From k-1 groups to k groups
    for k:=2; k<=K; k++ {
        for i:=0; i<len(A); i++ {
            for j:=i+1;j<len(A); j++ {
                // 1 group: A[i...j-1], k-1 groups: dp(j)
                dp[i]=max(dp[i], dp[j]+(presums[j]-presums[i])/float64(j-i))
            }
        }
    }
    return dp[0]
}

Solution: From left to right. Space: 2*n

// https://code.dennyzhang.com/largest-sum-of-averages
// Basic Ideas: DP
//
//  dp(i, k): nums[0...i], k
//
//    dp(j, k-1) + nums[j+1...i]
//
//    base condition: dp(i, 1)
//
// Complexity: Time O(K*n*n), Space O(n)
func max(x, y float64)float64 {
    if x>y {
        return x
    } else {
        return y
    }
}

func largestSumOfAverages(A []int, K int) float64 {
    presums := make([]float64, len(A)+1)
    for i, v := range A{
        presums[i+1] = presums[i] + float64(v)
    }
    dp := make([]float64, len(A))

    // base condition: with one group
    for i, _ := range dp {
        dp[i] = presums[i+1]/float64(i+1)
    }

    for k:=2; k<=K; k++ {
        dp2 := make([]float64, len(A))
        copy(dp2, dp)
        for i:=1; i<len(A); i++ {
            for j:=0; j<i;j++ {
                // k-1 group: dp[j], 1 group: A[j+1...i]
                dp2[i]=max(dp2[i], dp[j]+(presums[i+1]-presums[j+1])/float64(i-j))
            }
        }
        copy(dp, dp2)
    }
    return dp[len(A)-1]
}

Post Views: 4