leetcode

0

1 // Recursive

2 class Solution {

3 static double dp[101][101];

4

5 public:

6 Solution() { memset(dp, 0xFF, sizeof(dp)); }

7 double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) {

8 if (k == 0) return c == size(nums) ? 0 : -100000;

9 if (dp[k][c] == dp[k][c]) return dp[k][c];

10

11 double res = 0, sum = 0;

12 for (int i = c, j = 1; i < size(nums); i++, j++) {

13 sum += nums[i];

14 res = max(res, sum / j + largestSumOfAverages(nums, k - 1, i + 1));

15 }

16

17 return dp[k][c] = res;

18 }

19 };

20

21 double Solution::dp[101][101];

22

23 // Bottom-up DP

24 class Solution {

25 static double dp[101][101];

26

27 public:

28 double largestSumOfAverages(const vector<int> &nums, int k, int c = 0) {

29 static double sum[101], dp[101];

30 const int n = size(nums);

31

32 for (int i = 0, acc = 0; i < n; i++)

33 sum[i + 1] = acc += nums[i];

34 for (int i = 0; i < n; i++)

35 dp[i] = (sum[n] - sum[i]) / (n - i);

36

37 while (--k) {

38 for (int i = 0; i < n; i++) {

39 for (int j = i + 1; j < n; j++) {

40 dp[i] = max(dp[i], dp[j] + (sum[j] - sum[i]) / (j - i));

41 }

42 }

43 }

44

45 return dp[0];

46 }

47 };