How is this a dynamic programming problem?


Can somebody please explain?


I think it is a greedy problem…


It’s a “Longest increasing subsequences” problem, though it can be done without DP.


Can you explain how it is an LIS problem?


It’s not a LIS problem, i can prove you :slight_smile:


It isn’t bro. …


It is surely a dp problem. Have a look at my solution.

int Solution::maxProfit(const vector<int> &v) {
int n = v.size();

vector<vector<long long>>dp(2, vector<long long>(n+1, 0));

for(int i = n-1;i>-1;i--){
    dp[0][i] = max(v[i] + dp[1][i+1], dp[0][i+1]);//stock were in hand, we have a 
    //choice of selling them 
    //at current index
    //if no stocks in hand, we have a choice of buying one at current index
    dp[1][i] = max(-v[i] + dp[0][i+1], dp[1][i+1]);

return dp[1][0];



Dude if u want to write like that u used up space O(n) if u just use greedy it is O(1) with same time.