股票买卖

121. 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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

说你有一个由每天的股票价格组成的数组。如果你只能进行一次交易（比如购买或者销售一个股票），设计一个算法来获取最大利润。

例子1：

Input: [7, 1, 5, 3, 6, 4]

Output: 5 最大的利润为：6-1 = 5（不是7-1 = 6，因为销售价格需要比购买价格大）

例子2：

Input: [7, 6, 4, 3, 1]

Output: 0

这个例子中，无法进行交易，所以最大收益为0。

Solution

这道题乍一看需要 n*n 的循环去计算每出一个价格后的最优解，但是这样做时间复杂度太高，会超时，实际上也不用这么复杂。我们只需要每出一个新价格后，先判断这个价格减去我之前选择的买进价格后是否比之前的收益要大，以及这个新价格是否比我之前的买入价格要低，然后进行相应的操作即可，如果收益更大，就把这个收益记录下来，如果比买入价格低，就把买入价格换成这个价格。不需要担心这样直接换了之后往后计算的收益会不会不如之前，因为我们已经记录了在此之前的最大收益了，每次都会做对比的，而更换了更低的买入价格后，我们继续往后看能不能获得更大的收益，因为对于后面的数字来说这个数就是之前最小的买入价格了。其实想清楚后要进行的操作很简单，但如果想不清楚，就会觉得可能性太多了，要面面俱到总是会出问题，这里就要求头脑清晰了。

public class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        int small = 0;
        if (prices.length == 0) return 0;
        else small = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - small > result) result = prices[i] - small;
            if (prices[i] < small) small = prices[i];
        }
        return result;
    }
}

122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

意思是买卖股票时可以不计买卖次数，但是必须在买之前先把以前的股票卖掉。然后求能获利最大的额度。这样的话也很简单，只要遇见下一天的价格比这一天价格高的话，就卖出。

class Solution {
    public int maxProfit(int[] prices) {
        int total = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i + 1] > prices[i]) total += prices[i + 1] - prices[i];
        }
        return total;
    }
}