leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0813.cpp (1260B)

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 };