You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.
Note :
You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case or query contains an integer 'N' representing the total number of days for which you have stock prices.
The second line contains 'N' single space-separated integers representing the price of the stock on i-th day.
For each test case, print the maximum profit that you can earn.
Output for every test case will be printed in a separate line.
You are not required to print anything explicitly. Just implement the function.
1 <= t <= 10^2
0 <= N <= 10^5
Time Limit: 1 sec
1
7
1 2 3 4 5 6 7
6
We can make the maximum profit by buying the stock on the first day and selling it on the last day.
1
7
7 6 5 4 3 2 1
0
We can make the maximum profit by not buying the stock.
Try to consider all possibilities of buying and selling stocks and see which one gives you the maximum profit.
Let's say we have stock values of two days, say, [20, 30].
One must have to buy the stock first in order to sell it in the coming days.
So,
1. if I choose to buy the stock on first day for a value of 20 and sell it on the second day for a value of 30, I can earn a max profit of 10.
2. If I chose to skip day 1, then buying the stock on day 2 will put me in lose since there are no further days on which I can sell the stock. Hence, in this case, day 2 has to be skipped in order to make a max profit of 0.
Among these two scenarios, the first case yields me maximum profit and hence the answer.
This means, for every day, I may choose to buy or skip the stock. Once bought, I have to sell it in the following days to yield a max profit. Hence, to explore all the different possibilities,
O(N ^ N), Where N is the total number of days
Since for every index, you recurse on the array from that index till the end
O(N), Where N is the total number of days
Since at any time the maximum functions call that would exist in the stack will be N
All tags
Sort by
Interview problems
A very simple approch
long getMaximumProfit(long *values, int n)
{
long profitmoney=0;
for(int i=1;i<n;i++)
if(values[i]>values[i-1]) profitmoney+=values[i]-values[i-1];
// 7 is big 7-1 = 6, profit will be 4th no index and selling price id 7 .
return profitmoney;// so the total profit is 7-5 =1
}
Interview problems
C++|| 4 line of code || without dp /recu
long getMaximumProfit(long *values, int n)
{
long profitmoney=0;
for(int i=1;i<n;i++)
if(values[i]>values[i-1]) profitmoney+=values[i]-values[i-1];
return profitmoney;
}Interview problems
4 line Code By NK
long getMaximumProfit(long *values, int n)
{
long ans=0;
for(int i=0;i<n-1;i++){
if(values[i]<values[i+1]){
ans+=values[i+1]-values[i];
}
}
return ans;
}
Interview problems
Simple Solution | C++
long getMaximumProfit(long *values, int n)
{
//Write your code here
long ans = 0;
for(int i=n-2; i>=0; i--)
{
if(values[i] < values[i+1])
{
ans += (values[i+1] - values[i]);
}
}
return ans;
}Interview problems
why cant we use greedy approach?
long getMaximumProfit(long *v, int n)
{
//Write your code here
int a =0;
int ans=0,currp=0;
for(int i=1;i<n;i++){
int cost = v[i]-v[a];
currp = max(cost,currp);
if(v[i]<v[a]){
a=i;
}
if(v[i]>v[i+1]){
ans+=currp;
currp=0;
a=i+1;
}
}
ans+=currp;
return ans;
}
Interview problems
Best Time to Buy and Sell Stock II ( C++ Solution) TC(O(N))
/* Time Complexity : O(N ) Space Complexity : O(1) where N is the total number of days */
long getMaximumProfit(long *values, int n)
{
long maximumProfit = 0 ;
for(int i = 0 ; i < n - 1 ; ){
i++;
while( i < n && values[i] > values[i-1]){
maximumProfit += (values[i] - values[i-1]) ;
i++;
}
}
return maximumProfit ;
}
Interview problems
Best Time to Buy and Sell Stock II (JAVA Solution) (TC: O(N))
public class Solution {
public static long getMaximumProfit (int n, long[] values) {
long maxProfit = 0;
for(int i = 1; i < n; i++){
if(values[i] > values[i-1]){
maxProfit += (values[i]-values[i-1]);
}
}
return maxProfit;
}
}
Interview problems
simpliest method to solve BUY AND SELL STOCKS || time comp-O(N)
long profit=0;
for(int i=1;i<n;i++){
if(values[i]>values[i-1]){
profit+=values[i]-values[i-1];
}
}
return profit;
Interview problems
Best Time to Buy and Sell Stock II || Memoization || Tabulation || Space Optimization
#include <bits/stdc++.h>
long memo(int ind,int buy,long *values,int n,vector<vector<long>>&dp){
//base case
if(ind==n){
return 0;
}
if(dp[ind][buy]!=-1){
return dp[ind][buy];
}
long profit=0;
if(buy==0){
profit=max(0+memo(ind+1,0,values,n,dp),-values[ind]+memo(ind+1,1,values,n,dp));
}
if(buy==1){
profit=max(0+memo(ind+1,1,values,n,dp),values[ind]+memo(ind+1,0,values,n,dp));
}
return dp[ind][buy]=profit;
}
long getMaximumProfit(long *values, int n)
{
// vector<vector<long>>dp(n,vector<long>(2,-1));
// if(n==0){
// return 0;
// }
// long ans=memo(0,0,values,n,dp);
// return ans;
//tabulation
// vector<vector<long>>dp(n+1,vector<long>(2,0));
// dp[n][0]=dp[n][1]=0;
// for(int ind=n-1;ind>=0;ind--){
// for(int buy=0;buy<=1;buy++){
// long profit=0;
// if(buy==1){
// profit=max(0+dp[ind+1][1],-values[ind]+dp[ind+1][0]);
// }
// if(buy==0){
// profit=max(0+dp[ind+1][0],values[ind]+dp[ind+1][1]);
// }
// dp[ind][buy]=profit;
// }
// }
// return dp[0][1];
//space optimization
vector<long>prev(2,0),cur(2,0);
prev[0]=prev[1]=0;
for(int ind=n-1;ind>=0;ind--){
for(int buy=0;buy<=1;buy++){
long profit=0;
if(buy==1){
profit=max(0+prev[1],-values[ind]+prev[0]);
}
if(buy==0){
profit=max(0+prev[0],values[ind]+prev[1]);
}
cur[buy]=profit;
}
prev=cur;
}
return prev[1];
}
