Best Time to Buy and Sell Stock II

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Solution: The difference of this problem with previous one is that you can buy and sell stocks several times, instead of buying and selling for just once. Then how to find the purchasing and selling points? When you buy the stock, the time should be the day when the price is the lowest after the last selling transaction. When you sell the stock, the time should be the day when the price is the highest after the most recent purchasing time. Therefore, the idea is to find the last element of the non-decreasing sequence and choose it as the purchasing time (min), set the last element of non-increasing sequence after min as max, which is the selling time. Add the difference of max and min to sum, and set min to the value of max, and update it in the next iteration. Pay attention to the condition in the while loop, prevent i to be larger than or equal to the length of the array -1, otherwise you will get array out of bound exception and cause the run-time error.

01 public int maxProfit(int[] prices) {
02     if(prices.length<=1)
03     {
04         return 0;
05     }
06   
07     int min=prices[0];
08     int max=prices[0];
09     int i=0;
10     int sum=0;
11   
12     while(i<prices.length-1)
13     {
14         while(i<prices.length-1 && prices[i+1]<=prices[i])
15         {
16             i++;
17           
18         }
19         min=prices[i];
20         max=prices[i];
21         while(i<prices.length-1 && prices[i+1]>=prices[i])
22         {
23             i++;
24         }
25         max=prices[i];
26         sum+=max-min;
27         min=prices[i];
28     }
29   
30     return sum;
31 }