# Explanation of why the editorial solution approach 2 works.

• The below solution is inspired by the editorial solution approach 2. I could not figure it out myself. An explanation of why this solution works follows the solution.

``````public int maxProfit(int[] prices) {
if(prices==null || prices.length==0) return 0;
int i=0, profit=0;
while(i<prices.length){
while(i<prices.length-1 && prices[i+1]<=prices[i]) i++;
int valley = prices[i++];
while(i<prices.length-1 && prices[i+1]>=prices[i]) i++;
if(i<prices.length)
profit += prices[i]-valley;
}
return profit;
}
``````

Initially I was unable to wrap my head around this solution. I understood what was being done, but I failed to understand why it is the correct solution as I thought that it may not work for some test cases. My way of approaching this problem was by drawing a comparison between the profit that can be gained by using multiple transactions and the profit that can be gained by using a single transaction in the same given range. The above solution never does that. So why does it work?

Well, it works because of common sense. In a given range of prices, the profit gained by a single transaction will never exceed the profit from multiple transactions. Below is an extreme case where profit from a single transaction equals the profit from multiple transactions:

[1,2,2,3,3,4]
Max profit: 3 in any manner.

Except for such cases, a single transaction can never generate the same profit as multiple transactions in a given range. Things become clearer if you draw a graph.

So a comparison need not be drawn. Multiple transactions will always yield more profit.

This is an attempt to help anyone confused by the solution like I was. Please correct me if I made any mistake.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.