Skip to main content

Best Time to Buy and Sell Stock II | Leetcode 122 Solution

 122 . Best Time to Buy and Sell Stock II

   Memoization approach : 


You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

 

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 105


solution :

  Explanation: x = 0 means we are going to buy stock. since we have two choices we can buy a particular stock or buy stock from the remaining array.
so, I wrote the code :

if(x == 0)
        {
            return dp[i][x] = max(-prices[i] + solve(prices, i+1, size, 1, dp) , solve(prices , i+1 , size , 0 , dp));
        }

it means if we select that index and then change x = 1, that is next time we are going to sell it at a different price, and the second choice is we will buy from the remaining array. 

another return statement is for sell of the stock. this will also work in a similar way.

class Solution {
public:
    int solve(vector<int>& prices , int i , int size , int x , vector<vector<int>>&dp)
    {
        if(i == size )
        {
            return 0;
        }

        if(dp[i][x] != -1)
        {
            return dp[i][x];
        }
        if(x == 0)
        {
            return dp[i][x] = max(-prices[i] + solve(prices, i+1, size, 1, dp) , solve(prices , i+1 , size , 0 , dp));
        }

     
            return dp[i][x] = max(prices[i] + solve(prices , i+1 , size , 0 , dp), solve(prices , i+1, size , 1 , dp));

    }
    int maxProfit(vector<int>& prices) {


        int size = prices.size();
        int i =0;
        int x = 0;
        vector<vector<int>>dp(size+1 , vector<int>(2 , -1));
        return solve(prices , i, size , x, dp);
     
    }
};



Comments

Popular posts from this blog

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a"  Output: false  Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*"  Output: true  Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*"  Output: true  Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...