Need a unique gift idea?
A Pastebin account makes a great Christmas gift
SHARE
TWEET

Untitled

a guest Nov 16th, 2018 97 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
 
  1. double largestSumOfAverages(vector<int>& A, int K) {
  2.         vector<vector<double>> memo(K + 1, vector<double>(A.size(), numeric_limits<int>::min()));
  3.  
  4.         for (int k = 1; k <= K; ++k) {
  5.             for (int l = 0; l < A.size(); ++l) { // k-th segment left
  6.                 double curr_sum = 0;
  7.                 for (int r = l; r < A.size(); ++r) { // k-th segment right
  8.                     curr_sum += A[r];
  9.                     double curr_avg = curr_sum / (r - l + 1);
  10.                     double k_1_avg = l > 0 ? memo[k - 1][l - 1] : 0;
  11.                     memo[k][r] = max(memo[k][r], k_1_avg + curr_avg);
  12.                 }
  13.             }
  14.         }
  15.  
  16.         return memo.back().back();
  17.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top