Loading [MathJax]/extensions/AssistiveMML.js

By

文章目录

LeetCode地址：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    public int maxProfit(int[] prices) {
        int ret=0,
            buy=0,
            sale=0,
            length=prices.length;
        
        if(length<2)
            return ret;
        
        int[] historyProfit=new int[length];
        
        buy=prices[0];
        for(int i=1;i<length;i++)
        {
            historyProfit[i]=getMax(historyProfit[i-1], prices[i]-buy);
            buy=getMin(buy, prices[i]);
        }
        
        sale=prices[length-1];
        ret=historyProfit[length-1];
        for(int i=length-1;i>0;i--)
        {
            ret=getMax(ret, historyProfit[i-1]+sale-prices[i]);
            sale=getMax(sale, prices[i]);
        }
        
        return ret;
    }
    
    public int getMax(int a,int b)
    {
        return a>b?a:b;
    }
    
    public int getMin(int a,int b)
    {
        return a>b?b:a;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录