[Python] Divid and Conquer without DP, 100%
Idea\nCreate a helper function getValues(s, e) that returns a vector vals. \nvals[i] stores the maximum value that you can get from picking i coins from piles s
#### Idea\nCreate a helper function getValues(s, e) that returns a vector vals. \nvals[i] stores the maximum value that you can get from picking i coins from piles s, s+1, s+2, ..., e.\nWith the helper fucntion, the final result will be geValues(1, n)[k].\n\nThe basic case of getValues is when s equal to t. In this case, there is only one pile. Therefore, for vals[i], we just need to pick the first i coins.\nFor s < e, we split the piles into two parts ( (s, mid), (mid+1, e)) and get the values of both parts. \nWith the vals of left and right piles, we can calculate vals[i] by consider taking different j coins from the left part piles and take i-j coins from the right part piles and select the j that can have the maximum value.\n\n#### Complexity\n\nTime: O(K^2) \nThis method is better than the DP solution when sum(piles[i].length) is larger than 2000, such as sum(piles[i].length) = 20000.\nSpace: O(K)\n\n#### Code\n```\nclass Solution:\n    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:\n        \n        def getValues(s, e): # return maximum values of getting different numbers from pile s to plie e\n            if s == e: # only one piles\n                coin_num = min(len(piles[s]), k)\n                vals = [0] * (coin_num+1)\n                for i in range(1, coin_num + 1):\n                    vals[i] = (vals[i-1] + piles[s][i-1])\n                return vals\n            \n            # more than one piles\n            mid = (s+e)//2\n            left_vals = getValues(s, mid)\n            right_vals = getValues(mid+1, e)\n            \n            coin_num_l = len(left_vals) -1\n            coin_num_r = len(right_vals) -1\n            coin_num = min(k, coin_num_l+coin_num_r)\n            vals = [0] * (coin_num+1)\n            for i in range(1, coin_num+1): # calculate max value of picking i coins (vals[i])\n                vals[i] = -1\n                min_l = max(0, (i - coin_num_r)) # minimum coins that need to take from left in order to take i coins  from both sides \n                max_l = min(i, coin_num_l) + 1 # maxmum coins that need to take from left in order to take i coins  from both sides \n                for j in range(min_l, max_l): # consider the case of select j coins from the left side\n                    tmp = left_vals[j] + right_vals[i-j] \n                    if vals[i] < tmp:\n                        vals[i] = tmp\n            return vals\n        \n        vals = getValues(0, len(piles)-1)\n        \n        return vals[k]\n```
['Divide and Conquer', 'Python']