Best Time To Buy and Sell Stock
You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the number of possible transactions you can make.

Your task is to find the maximum profit in at most K transactions. A valid transaction involves buying a stock and then selling it.

Note

You can’t engage in multiple transactions simultaneously, i.e. you must sell the stock before rebuying it.

For Example

Input: N = 6 , PRICES = [3, 2, 6, 5, 0, 3] and K = 2. Output: 7 Explanation : The optimal way to get maximum profit is to buy the stock on day 2(price = 2) and sell it on day 3(price = 6) and rebuy it on day 5(price = 0) and sell it on day 6(price = 3). The maximum profit will be (6 - 2) + (3 - 0) = 7.

Input Format

The first line of input 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 contains two single-space separated integers ‘N’ and ‘K’, respectively. The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array 'PRICES'.

Output Format

For each test case, print a single integer denoting the maximum profit in at most K transactions. Print the output of each test case in a separate line.

Note

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints

1

Question

Best Time To Buy and Sell Stock

You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the number of possible transactions you can make.

Your task is to find the maximum profit in at most K transactions. A valid transaction involves buying a stock and then selling it.

Note

You can’t engage in multiple transactions simultaneously, i.e. you must sell the stock before rebuying it.

For Example

Input: N = 6 , PRICES = [3, 2, 6, 5, 0, 3] and K = 2.
Output: 7

Explanation : The optimal way to get maximum profit is to buy the stock on day 2(price = 2) and sell it on day 3(price = 6) and rebuy it on day 5(price = 0) and sell it on day 6(price = 3). The maximum profit will be (6 - 2) + (3 - 0) = 7.

Input Format

The first line of input 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 contains two single-space separated integers ‘N’ and ‘K’, respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array 'PRICES'.

Output Format

For each test case, print a single integer denoting the maximum profit in at most K transactions.

Print the output of each test case in a separate line.

Note

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints

1 <= T <= 100
1 <= N <= 5000
0 <= K <= N/2
0 <= ARR[i] <=10^5

Time Limit : 1 sec

Accepted Answer

Just maintain two pointers one for minimum price so far, and other to maintain max profit so far.
Code that i used.
int maxProfit(vector &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}

Accepted Answer

Recursion

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

Algorithm

We will call a maxProfit function that returns us the maximum profit we can get from the array starting from i (here i denotes the starting index of PRICES) to N - 1. We will use a bool variable buy. If buy == true it denotes that we had bought a stock and now we can’t buy another until we sell it and buy == false denotes that we hadn’t currently bought any stock. The maxProfit function will work as follows:

If K == 0 || i == N
- Return 0.
If buy == false
- We make a recursive call to i + 1 with buy marked as false. (Not holding the stock).
- We make a recursive call to i + 1 with buy marked as true and subtract PRICES[i]. (Buy stock on i -th day).
- We finally return the maximum of them.
Else
- We make a recursive call to i + 1 with buy marked as true. (Hold the stock).
- We make a recursive call to i + 1 with buy marked as false and add PRICES[i] and decrement K by 1. (Sell stock on i-th day).
- Return the maximum of them.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ denotes the number of elements in an array.

In the worst case, extra space is used by the recursion stack which can go up to a maximum depth of N. Hence the space complexity is O(N).

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where ‘N’ denotes the number of elements in an array.

In the worst case at every step, we are making two recursive calls and the maximum depth of the recursion tree can go up to N. Hence the time complexity is O(2 ^ N).

Accepted Answer

Memoization

If we draw the recursion tree for the recurrence relation of approach 1, we can observe that there are a lot of overlapping subproblems. There are only N * K distinct recursive calls.

Lets understand this by an example, consider PRICES = [5, 4, 8, 9] and K = 3 and buy == false.

The recursion tree for array will be

As we can clearly see in the recursion tree that [8, 9] for K == 3 and buy == true will be calculated twice.

Since the problem has overlapping subproblems, we can solve it more efficiently using memorization.

The algorithm is similar to the previous approach with some additions.

We initialize a 3-D vector memo with -1. Now, memo[i][j][0] will denote the maximum profit we can get from the array starting from ‘i’ to N - 1 in at most ‘j’ transactions considering currently we haven't bought the stock. memo[i][j][1] will denote the maximum profit we can get from the array starting from ‘i’ to N - 1 in at most ‘j’ transactions considering currently we have bought the stock.

Before calling the function for any valid (i, j, buy), we will check whether we already have a solution corresponding to the (i, j, m) present in memo.

If we already have a solution corresponding to (i, j, m), we return the solution.
Else
- If buy == 0
  - We call the recursive function for (i + 1, j, 0) and (i + 1, j, 1) - PRICES[i] and store the maximum of them in memo[i][j][buy] and return it.
- Else if buy == 1
  - We call the recursive function for (i + 1, j, 1) and (i + 1, j - 1, 0) + PRICES[i] and store the maximum of them in memo[i][j][buy] and return it.

Space Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the number of elements in an array and ‘K’ is the maximum number of transactions allowed.

We are memorising the result using N * K * 2 sized dp array. Also, in the worst case the size of the recursive stack can go up to N. Hence the space complexity is O(N * K).

Time Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the number of elements in an array and ‘K’ is the maximum number of transactions allowed.

In the worst case, there will be N * K distinct recursive calls. Hence the time complexity is O(N * K).

Python (3.5)

'''

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where N is the length of array/list and K

    is maximum number of transactions allowed.

'''





def maxProfit(prices, idx, n, buy, k, memo):



    if(idx == n or k == 0):

        return 0



    if(memo[idx][k][buy] != -1):

        return memo[idx][k][buy]



    if(buy == 0):

        memo[idx][k][buy] = max(maxProfit(prices, idx + 1, n, 0, k, memo), maxProfit(prices, idx + 1, n, 1, k, memo) - prices[idx])

        return memo[idx][k][buy]

    else:

        memo[idx][k][buy] = max(maxProfit(prices, idx + 1, n, 1, k, memo), maxProfit(prices, idx + 1, n, 0, k - 1, memo) + prices[idx])

        return memo[idx][k][buy]





def maximumProfit(prices, n, k):



    memo = [[[-1 for k in range(3)] for j in range(k + 2)] for i in range(n + 1)]



    return maxProfit(prices, 0, n, 0, k, memo)

Java (SE 1.8)

/*

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where N is the length of array and K

    is maximum number of transactions allowed.

*/



import java.util.*;



public class Solution

{

public static int maxProfit(int[] prices, int idx, int n, int buy, int k, int[][][] memo)

    {

        // If 'k' transactions is completed.

        if (idx == n || k == 0)

        {

            return 0;

        }



        // If result is already computed.

        if (memo[idx][k][buy] != -1)

        {

            return memo[idx][k][buy];

        }



        // If stock is not bought.

        if (buy == 0)

        {

            return memo[idx][k][buy] = Math.max(maxProfit(prices, idx + 1, n, 0, k, memo), maxProfit(prices, idx + 1, n, 1, k, memo) - prices[idx]);

        }



        // If stock is bought.

        else

        {

            return memo[idx][k][buy] = Math.max(maxProfit(prices, idx + 1, n, 1, k, memo), maxProfit(prices, idx + 1, n, 0, k - 1, memo) + prices[idx]);

        }

    }



public static int maximumProfit(int[] prices, int n, int k)

    {



        // Initialize 3-D array to store result of recursive calls.

        int[][][] memo = new int[n][k + 1][2];



        // Initialize all elements with -1.

        for (int i = 0; i < n; i++)

        {

            for (int j = 0; j < k + 1; j++)

            {

                Arrays.fill(memo[i][j], -1);

            }

        }



        // Recursive function to find profit.

        return maxProfit(prices, 0, n, 0, k, memo);

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where N is the length of array and K

    is maximum number of transactions allowed.

*/



int maxProfit(vector &prices, int idx, int n, int buy, int k, vector>> &memo)

{



    // If 'k' transactions is completed.

    if (idx == n || k == 0)

    {

        return 0;

    }



    // If result is already computed.

    if (memo[idx][k][buy] != -1)

    {

        return memo[idx][k][buy];

    }



    // If stock is not bought.

    if (buy == 0)

    {

        return memo[idx][k][buy] = max(maxProfit(prices, idx + 1, n, 0, k, memo), maxProfit(prices, idx + 1, n, 1, k, memo) - prices[idx]);

    }



    // If stock is bought.

    else

    {

        return memo[idx][k][buy] = max(maxProfit(prices, idx + 1, n, 1, k, memo), maxProfit(prices, idx + 1, n, 0, k - 1, memo) + prices[idx]);

    }

}



int maximumProfit(vector &prices, int n, int k)

{

    // Initialize 3-D array to store result of recursive calls.

    vector>> memo(n, vector>(k + 1, vector(2, -1)));



    // Recursive function to find profit.

    return maxProfit(prices, 0, n, 0, k, memo);

}

Accepted Answer

Bottom Up Approach

Initially, we were breaking the large problem into small subproblems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.

We initialize two 2-D matrices, buy[K+1][N+1] and sell[K+1][N+1]. Here, buy[i][j] will denote the maximum profit we can get in at most ‘i’ transactions from the array starting from index 0 and ending at index j -1 and the final state is buying the stock. sell[i][j] will denote the maximum profit we can get in at most ‘i’ transactions from the array starting from index 0 and ending at index j -1 and the final state is not holding the stock i.e. selling the stock.

Algorithm

We iterate the matrix buy and sell column-wise and update the values.
- buy[j][i] = max(buy[j][i-1], sell[j-1][i-1] - PRICES[i-1]). Here buy[j][j-1] denotes holding the stock and sell[j -1][i - 1] - PRICES[i -1] denotes buying the stock on i-th day.
- sell[j][i] = max(sell[j][i-1], buy[j][i-1]+PRICES[i-1]). Here sell[j][i-1] denotes not holding the stock and buy[i][j - 1] + PRICES[i -1] denotes selling the stock on i-th day.
Finally return sell[K][N].

Space Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the number of elements in an array and ‘K’ is the maximum number of transactions allowed.

We are using two dp matrices buy and sell of size N * K each. Hence, the space complexity is O(N * K).

Time Complexity: O(n^2)Explanation:

O(N * K), where ‘N’ denotes the number of elements in an array and ‘K’ is the maximum number of transactions allowed.

There is total (N + 1) * (K + 1) cells in the grid and we are traversing the grid.

Hence, the time complexity is O(N * K).

Python (3.5)

'''

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where N is the length of array/list and K

    is maximum number of transactions allowed.

'''





def maximumProfit(prices, n, k):



    buy = [[-1000000000 for j in range(n + 2)] for i in range(k + 2)]

    sell = [[0 for j in range(n + 2)] for i in range(k + 2)]



    for i in range(1, n + 1):



        for j in range(1, k + 1):



            buy[j][i] = max(buy[j][i - 1], sell[j - 1][i - 1] - prices[i - 1])

            sell[j][i] = max(buy[j][i - 1] + prices[i - 1], sell[j][i - 1])

        

    return sell[k][n]

Java (SE 1.8)

/*

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where 'N' is the length of array and K

    is maximum number of transactions allowed.

*/



import java.util.*;



public class Solution

{

public static int maximumProfit(int[] prices, int n, int k)

    {



        // Initialize 2-D array to store results.

        int[][] buy = new int[k + 1][n + 1];

        int[][] sell = new int[k + 1][n + 1];



        // Initialize all values of 'buy' with -1000000000.

        for (int i = 0; i < k + 1; i++)

        {

            Arrays.fill(buy[i], -1000000000);

        }



        // Initialize all values of 'buy' with 0.

        for (int i = 0; i < k + 1; i++)

        {

            Arrays.fill(sell[i], 0);

        }



        // Iterate from bottom to top.

        for (int i = 1; i <= n; i++)

        {

            for (int j = 1; j <= k; j++)

            {

                buy[j][i] = Math.max(buy[j][i - 1], sell[j - 1][i - 1] - prices[i - 1]);

                sell[j][i] = Math.max(buy[j][i - 1] + prices[i - 1], sell[j][i - 1]);

            }

        }



        // Last cell of 'sell' contains desired result.

        return sell[k][n];

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * K)

    Space Complexity : O(N * K)



    where N is the length of array and K

    is maximum number of transactions allowed.

*/





int maximumProfit(vector& prices, int n, int k)

{

	

	// Initialize 2-D array to store results.

    vector> buy(k + 1,vector(n + 1, -1000000000));

    vector> sell(k + 1,vector(n + 1, 0));

    

    // Iterate from bottom to top.

    for(int i = 1; i <= n; i++)

    {

        for(int j = 1; j <= k; j++)

        {

            buy[j][i] = max(buy[j][i - 1], sell[j - 1][i - 1] - prices[i - 1]);

            sell[j][i] = max(buy[j][i - 1] + prices[i - 1], sell[j][i - 1]);

        }

    }

    

    // Last cell of 'sell' contains desired result.

    return sell[k][n];

}

You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the number of possible transactions you can make.

Your task is to find the maximum profit in at most K transactions. A valid transaction involves buying a stock and then selling it.

Note

For Example

Input Format

Output Format

Note

Constraints

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer