# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/high_frequency/best_time_to_buy_and_sell_stock.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.