leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1043.cpp (606B)

      1 class Solution {
      2     int dp[501];
      3 
      4   public:
      5     Solution() { memset(dp, 0xFF, sizeof(dp)); }
      6     int maxSumAfterPartitioning(const vector<int> &arr, const int k, int idx = 0) {
      7         if (idx == arr.size()) return 0;
      8         if (dp[idx] != -1) return dp[idx];
      9 
     10         int maxi = arr[idx];
     11         int res = maxi + maxSumAfterPartitioning(arr, k, idx + 1);
     12         for (int i = idx + 1; i < idx + k && i < arr.size(); i++) {
     13             maxi = max(maxi, arr[i]);
     14             res = max(res, (i - idx + 1) * maxi + maxSumAfterPartitioning(arr, k, i + 1));
     15         }
     16 
     17         return dp[idx] = res;
     18     }
     19 };