求大神们给Stock带有fee的解题思路

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. int maxProfix(vector<int> &prices, int transactionFee) {
   
2. 
   
3.     int minP = prices[0], maxP = 0;
   
4.     int result = 0;
   
5.     for(int i = 1; i < prices.size(); ++i) {
   
6.         if(prices[i] > maxP) {
   
7.             maxP = prices[i];
   
8.         } else if(prices[i] < maxP) {
   
9.             if(maxP - prices[i] > transactionFee) {
   
10.                 if(maxP - minP > transactionFee) {
    
11.                     result += maxP - minP - transactionFee;
    
12.                     minP = prices[i];
    
13.                     maxP = prices[i];
    
14.                 }
    
15.             } else {
    
16.                 if(prices[i] < minP) {
    
17.                     minP = prices[i];
    
18.                     maxP = prices[i];
    
19.                 }
    
20.             }
    
21.         }
    
22.     }
    
23.     if(maxP - minP > transactionFee) result += maxP - minP - transactionFee;
    
24. 
    
25.     return result;
    
26. }
    
27. 
    
28. 
    
29. int main(char **argv, int argc)
    
30. {
    
31. 
    
32.     vector<int> nums1 = {1, 4, 3, 5, 7, 10, 6, 5, 4, 8, 9, 12, 11, 10, 9, 5};
    
33.     vector<int> nums2 = {1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 3, 4, 6, 7};
    
34.     int result = maxProfix(nums1, 3);
    
35.     cout << result << endl;
    
36. 
    
37.     return 0;
    
38. }

复制代码

akluffy 发表于 2015-10-20 04:31

谢谢你的代码，能不能稍微解释下为何这样就一定是最大的？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

akluffy 发表于 2015-10-21 01:28
我没有刻意往DP上面想general的答案。这代码也就适用于不限交易次数的情况下。

逻辑的核心就在于，

如果输入是 1 5 4 2 8呢。

getway32 发表于 2015-10-27 10:14
如果输入是 1 5 4 2 8呢。

1 5 4 2 8 ,

直接 8 - 1 - 3 = 4，或者5 - 1 - 3＝１加上 ,8-2-3 = 3，也是4.
所以两种都可以是因为5-2是3，等于交易费，所以交易两次跟一次实际上一样