How is this a dynamic programming problem?


#1

Can somebody please explain?


#2

I think it is a greedy problem…


#3

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


#4

Can you explain how it is an LIS problem?


#5

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


#6

It isn’t bro. …


#7

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

}


#8

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.