📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3531| 回复: 9
跳转到指定楼层
上一主题 下一主题
收起左侧

Best Time to Buy and Sell Stock V 一道买卖股票题的变种 求讨论求指导

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
最近刷到一道买卖股票的新变种,题目是这样的,当天允许买,卖或者不操作,可以同时持有多个股票,买卖次数不限,问最大收益。
比如:
[1,2,10,9],返回 16,-1-2+10+9
[16, 40, 33, 43, 87, 26, 22, 100], 返回159, -16-33+43+87-22+100

提交了DFS的答案会超时,tag的提示是priority_queue. 来问问大家看有没有什么想法.
FYI, 这是 lintcode Best Time to Buy and Sell Stock V


评分

参与人数 1大米 +1 收起 理由
14417335 + 1 给你点个赞!

查看全部评分


上一篇:还有一年毕业,刷题找实习找全职
下一篇:考考java基础,我来问你来答
推荐
 楼主| 吃不饱小姐 2019-1-7 22:20:38 | 只看该作者
全局:
geekzyj 发表于 2019-1-7 02:40
我也遇到了这个问题,楼主有没有思路啊

还没来得及看 最近比较忙
回复

使用道具 举报

🔗
 楼主| 吃不饱小姐 2019-1-6 14:38:21 | 只看该作者
全局:
额 尴了个尬 =。= 没有人有想法吗
回复

使用道具 举报

全局:
去leetcode 上查找同样的题,有人在discussion 里做过总结。这是greedy的题。
回复

使用道具 举报

🔗
 楼主| 吃不饱小姐 2019-1-6 22:01:10 | 只看该作者
全局:
Vincentapple 发表于 2019-1-6 17:08
去leetcode 上查找同样的题,有人在discussion 里做过总结。这是greedy的题。

噢 感谢 我去找一下看~
回复

使用道具 举报

全局:
我也遇到了这个问题,楼主有没有思路啊

评分

参与人数 1大米 +1 收起 理由
吃不饱小姐 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
Vincentapple 2019-1-7 03:30:31 | 只看该作者
全局:
check out the discussion here, https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems

评分

参与人数 1大米 +3 收起 理由
吃不饱小姐 + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
xys8628 2020-2-4 06:06:57 | 只看该作者
全局:
我也碰到这道题,没有思路哦
回复

使用道具 举报

🔗
pbdpbd123 2020-5-4 10:27:45 | 只看该作者
全局:
给个我自己写的DP解法吧
  1. public class Solution {
  2.     public int getAns(int[] a) {
  3.         int n = a.length;
  4.         if(n <= 1){
  5.             return 0;
  6.         }
  7.         int max = n/2 + 1;
  8.         int min = Integer.MIN_VALUE;
  9.         
  10.         // dp[i][j]: total value of relized(already sold) and unrealized(still holding the sotck) profit on day i with j stocks in hand
  11.         int[][] dp = new int[n][max];
  12.         for(int[] x : dp){
  13.             Arrays.fill(x, min);
  14.         }
  15.         dp[0][0] = 0;
  16.         dp[0][1] = 0;
  17.         
  18.         for(int i = 1; i < n; i++){
  19.             for(int j = 0; j < max; j++){
  20.                 // hold
  21.                 if(dp[i-1][j]!=min) {
  22.                     //                  unrealized stock value changes
  23.                     dp[i][j] = dp[i-1][j] + j *(a[i] - a[i-1]);
  24.                 }
  25.                
  26.                 /// buy one more
  27.                 if(j-1 >=0 && dp[i-1][j-1]!= min){
  28.                     //                                           unrealized stock value changes
  29.                     dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + (j-1) * (a[i] - a[i-1]));
  30.                 }
  31.                
  32.                 // sell one more
  33.                 if(j+1 < max && dp[i-1][j+1]!= min){
  34.                     //                                           unrealized stock value changes
  35.                     dp[i][j] = Math.max(dp[i][j], dp[i-1][j+1] + (j+1) * (a[i] - a[i-1]));
  36.                 }
  37.                
  38.                 //System.out.format("dp[%d][%d] = %d \n", i, j, dp[i][j]);
  39.             }

  40.         }
  41.         return dp[n-1][0];
  42.         
  43.     }
  44. }
复制代码

评分

参与人数 2大米 +11 收起 理由
rosaline1995 + 1 给你点个赞!
14417335 + 10

查看全部评分

回复

使用道具 举报

🔗
chuntakung 2022-1-21 17:03:41 | 只看该作者
全局:
提供一個解法

public class Solution {
    /**
     * @param a: the array a
     * @return: return the maximum profit
     */
    public int getAns(int[] a) {
        // write your code here
        if (a == null || a.length == 0) {
            return 0;
        }

        // dp[i][j] max cash in hand at ith day with j stocks holded
        int[][] dp = new int[a.length][a.length + 1];


        dp[0][0] = 0;
        dp[0][1] = -a[0];

        for (int i = 1; i < a.length; i++) {
            for (int j = 0; j <= i+1; j++) {
                dp[i][j] = Integer.MIN_VALUE;
                if (j <= i) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j]);
                }
                if (j+1 <= i) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j+1] + a[i]);
                }
                if (j >= 1 && j-1 <= i) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] - a[i]);
                }
            }
        }

        return dp[a.length-1][0];

    }
}
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表