public static int maxProfit(int[] prices) {
int totalProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
totalProfit += prices[i] - prices[i - 1];
}
}
return totalProfit;
}
Problem
Submissions
Hints & solutions
Discuss
Best Time to Buy and Sell
Moderate
0/80
Average time to solve is 20m
Contributed by
22 upvotes
Asked in companies
Problem statement
Note:
You must sell the stock before you buy it again.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains an integer value N, denoting the size of the input array.
The second line contains N single space-separated integers, denoting the prices on each day.
The only output line contains an integer, denoting the maximum profit.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 5 * 10^4
0 <= PRICES[i] <= 10^4
Time Limit: 1sec
Sample Input 1:
6
2 4 7 1 3 5
Sample Output 1:
9
Explanation for Sample Input 1:
As we are allowed to do any number of transactions to maximize the profit,
The first transaction we will do is to buy on day 1 (PRICE = 2) and sell on day 3 (PRICE = 7), making a profit of 5 (7 - 2).
The second transaction we will do is to buy on day 3 (PRICE = 1) and sell on day = 6 (PRICE = 5), making a profit of 4 (5 - 1).
Total profit = 5 + 4 = 9.
Sample Input 2:
4
1 2 3 4
Sample Output 2:
3
Hint
Hint 1
Hint 2
Hint 3
Hint 4
Calculate the profit corresponding to all the possible transactions and find out the maximum.
Approaches (4)
Approach 1
Approach 2
Approach 3
Approach 4
Recursive Approach
In this approach, we will be using recursion, where we will have a recursive method let's say MAX_PROFIT(PRICES, START) to find the maximum profit that we can make by doing any number of transactions starting from the START index.
To calculate this we will iterate on our prices starting from PRICES[START] till the last price. We will let the current price as the start of a transaction(buy price) and for each START, we will iterate over the next remaining prices and consider them as the end of the transaction(sell price). Let’s say the sell index ends. So the profit for this transaction is profit is PRICES[END] - PRICES[START]. Let it be equal to CURPROFIT (remember we will only choose that END index having price greater than the price of the START index. ).
Now we will calculate the maximum profit possible for the days after the ending day of the current transaction using recursion. So the PROFIT = CURPROFIT + MAX_PROFIT(PRICES, END + 1) and we will find the maximum of all possible profits.
Algorithm:
int MAX_PROFIT(PRICES, START):
- If there are no prices left to consider, Return.
- Initialize MAX with zero.
- For all prices i.e i from START to the SIZE - 1 index, where size denotes the size of the prices array. Buy the stock(start transaction).
- Initialize MAXPROFIT with zero.
- For remaining prices, j from i + 1 to SIZE - 1, Sell the stock(end transaction) if PRICE[j] > PRICE[i],
- CURPROFIT = PRICE[j] - PRICE[i].
- Calculate the maximum profit for the remaining prices and add to PROFIT, PROFIT += MAX_PROFIT(PRICES, j + 1).
- If PROFIT > MAXPROFIT , MAXPROFIT = PROFIT.
- If MAXPROFIT > MAX, MAX = MAXPROFIT.
- Return MAX.
Time Complexity
O(N^N), where N is the number of the days for which prices are given i.e the size of the input array.
In the worst case, the recursive function is called N^N times for every element in the array thus the time complexity here becomes O(N^N).
Space Complexity
O(N), where N is the number of the days for which prices are given i.e the size of the input array.
In the worst case, we will only be using the space required for the recursive stack to build.
Code Solution
(100% EXP penalty)
Best Time to Buy and Sell
All tags
Sort by
Interview problems
C++ solution
int profit=0;
for(int i=0;i<n-1;i++)
{
if(prices[i]<prices[i+1])
{
profit+=prices[i+1]-prices[i];
}
}
return profit;
} No
105 views
0 replies
0 upvotes
Interview problems
C++ Solution With 99.17% beats::
#include <bits/stdc++.h>
int maxProfit(int prices[], int n)
{
int profit=0;
for(int i=0;i<n-1;i++)
{
if(prices[i]<prices[i+1])
{
profit+=prices[i+1]-prices[i];
}
}
return profit;
}
77 views
0 replies
0 upvotes
Interview problems
Best Time to Buy and Sell
#include <bits/stdc++.h>
int maxProfit(int arr[], int n)
{
int profit=0;
for(int i=0; i<n-1; i++)
{
if(arr[i+1]>arr[i])
profit=profit+arr[i+1]-arr[i];
}
return profit;
}
112 views
0 replies
0 upvotes
Interview problems
Easy C++ solution using Recursion + Memoisation
#include <bits/stdc++.h>
int solve(int prices[],int n,int i,int buy,vector<vector<int>> &dp)
{
if(i>=n)return 0;
int profit=0;
if(dp[i][buy] != -1)
{
return dp[i][buy];
}
if(buy)
{
int buykro = -prices[i]+solve(prices,n,i+1,0,dp);
int skipkro = solve(prices,n,i+1,1,dp);
profit = max(buykro,skipkro);
}
else{
int sellkro = prices[i]+solve(prices,n,i+1,1,dp);
int skipkro = solve(prices,n,i+1,0,dp);
profit = max(sellkro,skipkro);
}
return dp[i][buy] = profit;
}
int maxProfit(int prices[], int n)
{
// Write your code here.
vector<vector<int>>dp(n+1,vector<int>(2,-1));
return solve(prices,n,0,1,dp);
}
144 views
0 replies
0 upvotes
Interview problems
Discussion thread on Interview Problem | Best Time to Buy and Sell
Hey everyone, creating this thread to discuss the interview problem - Best Time to Buy and Sell.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Best Time to Buy and Sell
193 views
3 replies
0 upvotes
Javascript (node v10.20.0)
Console