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.

因为只能交易一次，所以肯定要把当前价的前一位价格和已知的最低价求差值，得到的利润值（也就是当前价格下能获取的最大利润）和已知最大利润比较，其中大的那个就是最大利润了。 注意边界条件，利润为负返回0 （亏本生意不做）

public int maxProfit(int[] prices) {
    if (prices.length < 2) {
        return 0;
    }
    int minPrice = prices[0];
    int maxProfit = prices[1] - prices[0];
    for (int i = 2; i < prices.length; i++) {
        minPrice = Math.min(minPrice, prices[i-1]);
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
    }
    return maxProfit > 0 ? maxProfit : 0;
}

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 (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).

现在允许交易多次了，继续求最大利润。把每天的利润（亏本生意不做）加起来求和就是最大利润。

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