首页 > 代码库 > [leetcode] Best Time to Buy and Sell Stock III

[leetcode] Best Time to Buy and Sell Stock III

2024-07-02 17:22:31   222人阅读

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

给定一个数组，第i个元素代表股票在第i天的价格，限定最多交易两次，求最大收益。

由于两次交易不能重叠，可以把数组切分成两部分，分别计算第一次交易能够获取的最大利益，和第二次交易能够获取的最大利益，然后把它们相加。

计算第二次的时候，可以从后往前计算，并保存最高卖出价，可以简化计算。

代码如下:

 1 class Solution {
 2 public:
 3     int maxProfit(vector<int> &prices) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         int profit = 0, n = prices.size();
 7         if (n == 0) {
 8             return 0;
 9         }
10         int l[n], r[n];
11         l[0] = 0;
12         r[n-1] = 0;
13         int minp = prices[0];
14         for (int i = 1; i < n; i++) {
15             l[i] = max(prices[i] - minp , l[i - 1]);        
16             minp = min(prices[i] , minp);
17         }
18         int maxp = prices[n - 1];
19         for (int i = n - 2; i >= 0; i--) {
20             r[i] = max(maxp - prices[i] , r[i + 1]);
21             maxp = max(prices[i] , maxp);
22         }
23         for (int i = 0; i < n; i++) {
24             profit = max(l[i] + r[i] , profit);
25         }
26         return profit;      
27     }
28 };

在这道题中，发现g++中在栈里面开辟数组居然可以不用限定编译时必须确定数组的值，也就是说下面的代码是合法的。

 1 #include <iostream>
 2 using namespace std;
 3 int main(int argc, char *argv[])
 4 {
 5     int n;
 6     cin >> n;
 7     int a[n];
 8     for( int i = 0 ; i < n ; i++ )
 9     {
10         a[i] = i;
11         cout<<a[i];
12     }
13 }

原来C99标准对数组进行了加强：

C99中，程序员声明数组时，数组的维数可以由任一有效的整型表达式确定，包括只在运行时才能确定其值的表达式，这类数组就叫做可变长数组，但是只有局部数组才可以是变长的。可变长数组的维数在数组生存期内是不变的，也就是说，可变长数组不是动态的。可以变化的只是数组的大小。可以使用*来定义不确定长的可变长数组。

 

 

　　 　　


联系
我们