> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/high_frequency/best_time_to_buy_and_sell_stock.md).

# Best Time to Buy and Sell Stock

## Question

<http://www.lintcode.com/en/problem/best-time-to-buy-and-sell-stock/>

> 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.
>
> Example
>
> Given an example \[3,2,3,1,2], return 1

## Analysis

最初的想法是问题可以转化一下：计算相邻两天的变化量array，再对这个差值array寻找maximum subarray，得到的maximum也就是对应的maximum profit

另一种想法是：仅记录loop过的历史最小值，再寻找当前profit最大值.

Time complexity: `O(n)`. Only a single pass is needed.

Space complexity: `O(1)`. Only two variables are used.

## Solution

```java
// Diff + Maximum Subarray

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int[] diff = new int[prices.length];

        diff[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            diff[i] =  prices[i] - prices[i - 1];
        }
        return maxSubArray(diff);

    }

    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum = sum + nums[i];
            max = Math.max(sum, max);
            sum = Math.max(sum, 0);
        }
        return max;
    }
}
```

One pass - record lowest price O(n) (1ms 99.88% AC)

```java
class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            if (price < minPrice) minPrice = price;
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        return maxProfit;
    }
}
```

One Pass

```java
// Only remember the lowest price

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        // Only remember the smallest price
        int min = Integer.MAX_VALUE;  
        int profit = 0;
        for (int i : prices) {
            min = i < min ? i : min;
            profit = (i - min) > profit ? i - min : profit;
        }

        return profit;
    }
}
```

## Reference

Best Time to Buy and Sell Stock Series: I, II, III, IV

[来自梁佳宾的网络日志: Best Time to Buy and Sell Stock I II III IV](http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html)

[LeetCode Solution](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/solution/)