Best Time to Buy and Sell Stock

Today lets see one of the basic array problem,

for Best Time to Buy and Sell Stock problem we need to find best day to buy (low price ) and the best day to sell (high price) so we get maximum profit

The rule is simple we can't sell without buying, i.e sell should be after buying

lets solve this using both java and dart

Java

public class StockBuyAndSell {
  public static void main(String[] args) {
    int[] prices = new int[] {7, 1, 5, 3, 6, 4};
    int rightIndex=0;
    int min = Integer.MAX_VALUE;
    int maxProfit = 0;
    while(rightIndex<prices.length){
        if(prices[rightIndex]<min){
            min=prices[rightIndex];
        }
        maxProfit = Math.max(maxProfit,prices[rightIndex]-min);
        rightIndex++;
    }
    System.out.println(maxProfit);
  }
}

here we have the stock price list int[] prices = new int[] {7, 1, 5, 3, 6, 4};

lets create an pointer int rightIndex=0, lets create a min with Integer.MAX_VALUE and maxProfit with zero

we are going to iterate the array from the first to last(for loop ,while loop anything is fine), the idea behind this is we need to find the min value in the array and then we will find the difference between the min and current element, and we used Math.Max() to find whether current difference is maximum profit or the previous one and at last we print the maxProfit

Dart

 import 'dart:math';
  void main(){
    List<int> price = [7,1,5,3,6,4];
    int min=double.maxFinite.toInt();
    int maxProfit=0;
    for(int i=0;i<price.length;i++){
      if(min>price[i]){
        min=price[i];
      }
      maxProfit = max(maxProfit, price[i]-min);
    }
    print(maxProfit);
  }

In Dart we don't have min and max values for int so we used double and converted to int

Time Complexity:- O(n)
Auxiliary Complexity:- O(1)