@@ -0,0 +1,2208 @@
+/*%0A121. Best Time to Buy and Sell Stock%0AEasy%0A%0ASay you have an array for which the ith element is the price of a given stock on day i.%0A%0AIf you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.%0A%0ANote that you cannot sell a stock before you buy one.%0A%0AExample 1:%0A%0AInput: %5B7,1,5,3,6,4%5D%0AOutput: 5%0AExplanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.%0A             Not 7-1 = 6, as selling price needs to be larger than buying price.%0AExample 2:%0A%0AInput: %5B7,6,4,3,1%5D%0AOutput: 0%0AExplanation: In this case, no transaction is done, i.e. max profit = 0.%0A%0A****************************%0A%0AAll the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for %7B1, 7, 4, 11%7D, if he gives %7B0, 6, -3, 7%7D, you might end up being confused.%0A%0AHere, the logic is to calculate the difference (maxCur += prices%5Bi%5D - prices%5Bi-1%5D) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.%0A%0A*maxCur = current maximum value%0A*maxSoFar = maximum value found so far%0A%0AA more clear explanation on why sum of subarray works.:%0A%0ASuppose we have original array:%0A%5Ba0, a1, a2, a3, a4, a5, a6%5D%0A%0Awhat we are given here(or we calculate ourselves) is:%0A%5Bb0, b1, b2, b3, b4, b5, b6%5D%0A%0Awhere,%0Ab%5Bi%5D = 0, when i == 0%0Ab%5Bi%5D = a%5Bi%5D - a%5Bi - 1%5D, when i != 0%0A%0Asuppose if a2 and a6 are the points that give us the max difference (a2 %3C a6)%0Athen in our given array, we need to find the sum of sub array from b3 to b6.%0A%0Ab3 = a3 - a2%0Ab4 = a4 - a3%0Ab5 = a5 - a4%0Ab6 = a6 - a5%0A%0Aadding all these, all the middle terms will cancel out except two%0Ai.e.%0A%0Ab3 + b4 + b5 + b6 = a6 - a2%0A%0Aa6 - a2 is the required solution.%0A%0Aso we need to find the largest sub array sum to get the most profit%0A*/%0A%0Aclass Solution %7B%0A    public int maxProfit(int%5B%5D prices) %7B%0A        int maxCur = 0, maxSoFar = 0;%0A        for(int i = 1; i %3C prices.length; i++) %7B%0A            maxCur = Math.max(0, maxCur += prices%5Bi%5D - prices%5Bi-1%5D);%0A            maxSoFar = Math.max(maxCur, maxSoFar);%0A        %7D%0A        return maxSoFar;%0A    %7D%0A%7D

add p121