Largest Sum of Averages LeetCode solution in C++

1
class Solution {
2
 public:
3
  double solve(vector<int> &nums, int index, int k, vector<vector<double>> &dp) {
4
    if (index < 0) return 0;
5
    if (k <= 0) return -1e8;
6

7
    if (dp[index][k] != -1) return dp[index][k];
8

9
    double s_sum = 0;
10
    double maxi = INT_MIN;
11
    int cnt = 1;
12
    for (int i = index; i >= 0; i--) {
13
      s_sum += nums[i];
14
      maxi = max(maxi, (s_sum / cnt) + solve(nums, i - 1, k - 1, dp));
15
      cnt++;
16
    }
17
    return dp[index][k] = maxi;
18
  }
19

20
  double largestSumOfAverages(vector<int> &nums, int k) {
21
    int n = nums.size();
22
    vector<vector<double>> dp(n, vector<double>(k + 1, -1));
23
    return solve(nums, n - 1, k, dp);
24
  }
25
};