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

目前看面经，会遇到buy and sell

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 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. }

复制代码

写了一个，不确定是否能cover所有情况，请大家帮忙看看

1. class Solution {
   
2.   
   
3.   public int getProfit(int[] prices, int fee) {
   
4.     if (prices == null || prices.length == 0) return 0;
   
5.     int afterBuy = -prices[0];
   
6.     int afterSell = 0;
   
7.     for (int i = 1; i < prices.length; i++) {
   
8.       int oldBuy = afterBuy;
   
9.       int oldSell = afterSell;
   
10.       afterBuy = Math.max(oldBuy, oldSell - prices[i]);
    
11.       afterSell = Math.max(oldSell, oldBuy + prices[i] - fee);
    
12.     }
    
13.     return afterSell;
    
14.   }
    
15.   
    
16.   public static void main(String[] args) {
    
17.     Solution s = new Solution();
    
18.     System.out.println(s.getProfit(new int[]{1, 5, 4, 8, 3}, 3));
    
19.   }
    
20. }
    

复制代码

buy stock i 还是 II啊？

majiamajia 发表于 2015-10-16 01:10
buy stock i 还是 II啊？

应该是II，不限制交易次数，但是每次卖出就会有一个定额的费用。

还是可以根据IV，给出有gap，有fee的万能解法吧？转移方程改一改就是了

坐看云起 发表于 2015-10-16 02:24
还是可以根据IV，给出有gap，有fee的万能解法吧？转移方程改一改就是了

IV里不是定下了最多交易次数么，那这里就直接把它设成总共的天数么？

LosivE 发表于 2015-10-16 03:10
IV里不是定下了最多交易次数么，那这里就直接把它设成总共的天数么？

对的，IV可以引伸出很多万能解法：天数上限，再次购买间隔，还有交易费用

坐看云起 发表于 2015-10-16 03:30
对的，IV可以引伸出很多万能解法：天数上限，再次购买间隔，还有交易费用

能不能说说思路？感觉不好弄啊，这种general的情况

您好！
本帖隐藏的内容需要积分高于 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