121题目

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.

Example 1:

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

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

1
2
3
4
Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

121大意

给定一个序列，序列的值代表股票的值，求出最大的收益（只能交易一次）。

121 答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len =prices.size();
        int res=0;
        int minindex=0;
        for(int i=1;i<len;i++)
        {
            if(prices[i]>prices[minindex])
            {
                res =max(res,prices[i]-prices[minindex]);
            }
            else
            {
                minindex=i;
            }
        }
        return res;
    }
};

121解析

此题就是选择买入卖出股票的最大收益，对于第i天卖出的最大收益即为第i天的股市价格减去[0,i-1]天内的最小股市价格，当第i天的股市价格比前面最低股市价格还低，则更新最低股市价格。然后取最大的股市收益，为DP问题。用profit[i]表示第i天的收益，则minBuyPrice = min(minBuyPrice, prices[i]),并且profit[i] = prices[i]-minBuyPrice. 然后取profit中的最大值。

profit[i]即为dp数组，表示的是以第i天卖出去的最大的收益，所以profit[i] 的值就等于第i天的价格减去前面最低的价格，要是第i的价格比前面所有的都低，则更新最低的价格，并记录当前的节点。

122题目

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

122大意

一个数组仍代表股票序列，这次可以有无数次的交易机会

122答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len =prices.size();
        int res=0;
        for(int i=0;i<len-1;i++)
        {
            if(prices[i+1]-prices[i]>0)
            {
                res = res + prices[i+1]-prices[i];
            }
        }
        return res;
    }
};

122 解析

因为有无数次的交易机会，这道题的解法不是动态规划了，而是贪心，遍历数组，只要当前的值比上一个大，就进行一次买入卖出的操作，最后统计整体的收入。

123 题目

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

123 大意

还是股票数组，这次要求只能交易两次。

123思路

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
for(int i=1;i<len;i++)
{
  if(prices[i]>=prices[minindex])
  {
    dpzheng[i]=prices[i]-prices[minindex]
  }
  else
  {
    minindex = i;
    dpzheng[i]=0;
  }
}
int maxindex=len-1;
for(int i=len-2;i>=0;i--)
{
  if(prices[i]<=prices[maxindex])
  {
    dpfan[i]=prices[maxindex]-prices[i];
  }
  else
  {
    dpfan[i]=0;
    maxindex=i;
  }
 }

上面的代码是本题的基本思路，可以看成是121题的变形，两次股票交易是可以定义一个交易点，在这个点之前可以进行一次交易，在这个点之后可以进行一次交易。

定义一个dpzheng[]数组用来存以i为结束的最大收益，从前往后遍历，minindex记录最小值的位置。

再定义一个dpfan[]数组用来存以i为开始的最大收益，从后往前遍历，若price[i]< price[max],则相减就是获利值，若price[i]>price[max],获利是0，且更新最大值的位置。

这样求出的dpzheng[] 数组存的都是以i为结束的最大获利，dpfan[i]存的都是以i开始的最大获利值。

但是这样还不对。

123 答案

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len==0) return 0;
        //zheng数组表示的是以i为结束的dpzheng[]的最大值，
      	//fan数组表示的值以i为开始的dpfan[]的最大值。
      	//这样求出来的zheng数组和fan数组才是最后能获利的最大值。
      	//这样做的原因是假设第一步交易和第二步交易不一定是重合的，
      	//也就是说在某个点卖出以后，并不一定马上进行第二步交易，
      	//所以需要转换一下，使zheng[] 和fan[]存的都是历史的最大值。
      	//这样，遍历zheng[i]+fan[i]才是最大值。
        vector<int> zheng(len,0);
        vector<int> fan(len,0);
        int reszheng=0,resfan=0;
        int minindex=0;
        int zhengmax=0,fanmax=0;   
        for(int i=1;i<len;i++)
        {
            if(prices[i]>=prices[minindex])
            {
                reszheng=(prices[i]-prices[minindex]);
                zhengmax =max(zhengmax,reszheng);
                zheng[i]=zhengmax;
            }
            else
            {
                minindex = i;
                reszheng=0;
                zhengmax =max(zhengmax,reszheng);
                zheng[i]=zhengmax;
            }
        }
        int maxindex=len-1;
        for(int i=len-2;i>=0;i--)
        {
            if(prices[i]<=prices[maxindex])
            {
                //dpfan[i]=prices[maxindex]-prices[i];
                resfan=(prices[maxindex]-prices[i]);
                fanmax =max(fanmax,resfan);
                fan[i]=fanmax;
            }
            else
            {
                maxindex=i;
                resfan=0;
                fanmax =max(fanmax,resfan);
                fan[i]=fanmax;
            }
        }
        int res=0;
        for(int i=0;i<len;i++)
        {
            res=max(res,zheng[i]+fan[i]);
        }
        return res;
    }
};

参见

1
blog.csdn.net/u012501459/article/details/46514309