bottom.py

class Solution:
    def largestSumOfAverages(self, a: List[int], k: int) -> float:
        cusum = list(itertools.accumulate([0]+a))
        N=len(a)
        #dp[0][k] means from 0 to N-1 inclusively we have at most k groups
        # dp[0][k] = maximum of below cases
        #average(a[:1])+dp[1][k-1] from 1 to N-1 inclusively we have at most k-1 groups
        #average(a[:2])+dp[2][k-1] from 2 to N-1 inclusively we have at most k-1 groups
        #...
        #average(a[:N-1])+dp[N-1][k-1] from N-1 to N-1 inclusively we have at most k-1 groups
        # dp[1][k-1] from 1 to N-1 inclusively we have at most k-1 groups
        # average(a[1:2])+dp[2][k-2]
        # average(a[1:3])+dp[3][k-2]
        # ...
        # average(a[1:N-1])+dp[N-1][k-2]
        # until now, the solution can be clear. We should maintain a 2D dp table
        # dp[i][k] it means maximum average sum 
        #     from index i to N-1 inclusively, we have at most k groups
        # we can do it bottom up or top down
        # we can use cusum to speed up the average operation.
        dp = [[0]*(k+1) for i in range(len(a))]
        # the very bottom case will be k is 1, it means we only have one group from i to N-1 inclusively
        for at_most_group in range(1, k+1):
            for begin_i in range(N):
                if at_most_group == 1:
                    dp[begin_i][at_most_group] = (cusum[-1]-cusum[begin_i])/(N-begin_i)
                else:
                    this_res = []
                    for j in range(begin_i, N):
                        # we divide at_most_group to 1+(at_most_group-1)
                        # (at_most_group-1) is already caculated. 
                        # for eaxmple, dp[3][2] means 
                        # we are dividing list a from index 3 to N-1 into at most 2 groups
                        # if we pick up index 3 to 4 as first group, then we still need dp[5][1]
                        # dp[5][1] means we begin from index 5, we need at most 1 group.
                        # dp[5][1] is already caculated as k is from smaller to larger.
                        first_group_ave = (cusum[j+1]-cusum[begin_i])/(j-begin_i+1)
                        if j+1<N:
                            this_res.append(first_group_ave+dp[j+1][at_most_group-1])
                        else:
                            this_res.append(first_group_ave)
                    dp[begin_i][at_most_group] = max(this_res)
        # final result will be begin at 0 and at most it has k groups.
        return dp[0][k]