【leetcode】No.123：bast-time-to-bu

题目描述

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

思路

动态规划的思想，两次交易共有四种状态

• 第一次买：buy1=max(buy1,-prices[i])
• 第一次卖：sell1 = max(sell1,prices[i]+buy1);
• 第二次买：buy2 = max(buy2,sell1-prives[i]);
• 第二次卖：sell2=max(sell2,buy2+prices[i]);

对每一次可能进行的交易始终保持利润最大就可以。

代码

public class Solution {
    public int maxProfit(int[] prices) {
        int firstBuy = Integer.MIN_VALUE, firstSell = 0, secondBuy = Integer.MIN_VALUE, secondSell = 0;
        for (int price : prices){
            firstBuy = Math.max(firstBuy, -price);
            firstSell = Math.max(firstSell, firstBuy + price);
            secondBuy = Math.max(secondBuy, firstSell - price);
            secondSell = Math.max(secondSell, secondBuy + price);
        }
        return secondSell;
    }
}

题目描述

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

思路

每次更新目前的价格，只要递增就可以一直算收益，遇到递减不管就可以

代码

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

题目描述

Say you have an array for which the i th 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.

思路

一次交易就很简单，保存min和sum。更新最小值，遇到正收益就计算，与当前最大收益比较一下，收益大就替换

代码

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length<1) return 0;
        int sum = 0, min = prices[0];
        for (int i=0; i<prices.length; i++){
            if (prices[i] < min) min = prices[i];
            else if (prices[i] > min) sum = Math.max(sum, prices[i] - min);
        }
        return sum;
    }
}