[LeetCode-121] Best Time to Buy and Sell Stock 买卖股票的最佳时间

best-time-to-buy-and-sell-stock-i

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.

假设你有一个数组，里面存放的第i个元素表示第i天的股票的价格，如果你最多只允许进行一次交易（买进和卖出股票视为一次交易）

请设计一个算法得到最大利润。

这道题相当简单，感觉达不到Medium的难度，只需要遍历一次数组，用一个变量记录遍历过数中的最小值，然后每次计算当前值和这个最小值之间的差值最为利润，然后每次选较大的利润来更新。当遍历完成后当前利润即为所求，代码如下：

public class maxProfit {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0 )
            return 0;
        int min = prices[0];
        int maxprofit = 0;
        for (int i=0;i<prices.length;i++) {
            if (prices[i] < min) {
                min = prices[i];
            }
            if (prices[i] - min >maxprofit) {
                maxprofit = prices[i] - min;
            }
        }

        return maxprofit;
    }
}

best-time-to-buy-and-sell-stock-ii

Say you have an array for which the i ^th 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 (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

判断相邻是否递增，因为连续递增可以合起来看为一次买入卖出操作，所以统计所有递增量即可

public class bestTimeToBuyAndSellStockii {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0 )
            return 0;
        int profit = 0;
        for (int i=0;i<prices.length-1;i++) {
            if (prices[i] < prices[i+1]) {
                profit += prices[i+1] - prices[i];
            }
        }
        return profit;
    }
}

best-time-to-buy-and-sell-stock-iii（hard）

（第一次没做出来）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

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

Design an algorithm to find the maximum profit. You may complete at most two transactions.

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int buy1 = INT_MIN, sell1 = 0, buy2 = INT_MIN, sell2 = 0;
        for(int i = 0; i < prices.size(); i++) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

best-time-to-buy-and-sell-stock-IV（hard）