A person buys shares in the morning and sells them in the same day. He can make maximum two transactions of this type in a day. The second transaction must start after the first one has finished, so the actions are: buy, sell, buy sell. You receive the stock prices throughout the day and have to find the maximum profit a trader can make.
Input: int[] price = {4, 28, 11, 9, 7, 30, 75}; Output: 92 Explanation: The 2 transactions are: buy at 4 and sell at 28 and buy at 7 and sell at 75. This translates into: - 4 + 28 – 7 + 75 = 92. |
Solution:
1. static int maxProfit(int[] price) { 2. int length = price.length; 3. int[] profit = new int[length]; 4. 5. int maxPrice = price[length - 1]; 6. for (int i = length - 2; i >= 0; i--) { 7. if (price[i] > maxPrice) { 8. maxPrice = price[i]; 9. } 10. profit[i] = Math.max(profit[i + 1], maxPrice - price[i]); 11. } 12. 13. int minPrice = price[0]; 14. for (int i = 1; i < length; i++) { 15. if (price[i] < minPrice) { 16. minPrice = price[i]; 17. } 18. profit[i] = Math.max(profit[i - 1], profit[i] + (price[i] - minPrice)); 19. } 20. return profit[length - 1]; 21. } 22.