Best Time to Buy and Sell Stock 解答

Question

Say you have an array for which the ith 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

Key to the problem is to record money that we buy the stock.

For each element prices[i], we need to compare it with current buy-in price "buyIn":

If prices[i] > buyIn, we calculate the profit and compare it with current profit.

If prices[i] < buyIn, we set prices[i] as new buyIn.

Time complexity O(n), space cost O(1)

 1 public class Solution {
 2     public int maxProfit(int[] prices) {
 3         if (prices == null || prices.length < 2)
 4             return 0;
 5         int result = Integer.MIN_VALUE;
 6         int buyIn = prices[0], length = prices.length;
 7         for (int i = 1; i < length; i++) {
 8             if (prices[i] > buyIn)
 9                 result = Math.max(result, prices[i] - buyIn);
10             else
11                 buyIn = prices[i];
12         }
13         if (result < 0)
14             result = 0;
15         return result;
16     }
17 }