Partition Array for Maximum Sum Solutions in C++

/// Source : https://leetcode.com/problems/partition-array-for-maximum-sum/
/// Author : liuyubobobo
/// Time   : 2019-05-11

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(|A|^2)
/// Space Complexity :O(|A|)
class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {

        vector<int> dp(A.size(), -1);
        return dfs(A, 0, K, dp);
    }

private:
    int dfs(const vector<int>& A, int start, int K, vector<int>& dp){

        if(start == A.size()) return 0;
        if(dp[start] != -1) return dp[start];

        int maxv = A[start];
        int res = 0;
        for(int end = start; end <= min(start + K - 1, (int)A.size() - 1); end ++){
            maxv = max(maxv, A[end]);
            res = max(res, maxv * (end - start + 1) + dfs(A, end + 1, K, dp));
        }
        return dp[start] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/partition-array-for-maximum-sum/
/// Author : liuyubobobo
/// Time   : 2019-05-19

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(|A|^2)
/// Space Complexity :O(|A|)
class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {

        vector<int> dp(A.size());
        for(int i = 0; i < A.size(); i ++){

            int curMax = 0;
            for(int k = 1; k <= K && i - k + 1 >= 0; k ++){
                curMax = max(curMax, A[i - k + 1]);
                dp[i] = max(dp[i], (i >= k ? dp[i - k] : 0) + curMax * k);
            }
        }
        return dp[A.size() - 1];
    }
};


int main() {

    return 0;
}