Chinaunix首页 | 论坛 | 博客
  • 博客访问: 128021
  • 博文数量: 41
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 407
  • 用 户 组: 普通用户
  • 注册时间: 2013-06-27 13:42
文章分类

全部博文(41)

文章存档

2016年(1)

2015年(18)

2014年(22)

我的朋友

分类: C/C++

2014-09-16 17:27:04

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

***************************************************************************

分析:

    设状态f(i),表示区间[0,i]的最大利润,状态g(i),表示区间[i,n]的最大利润,则最终答案为max(f(i) +g(i))

***************************************************************************

代码:

    int maxProfit(vector &prices) {
        if (prices.size() < 2) return 0;
        vector f(prices.size(), 0);
        vector g(prices.size(), 0);
        for (int i = 1, valley = prices[0]; i < prices.size(); ++i) {
            valley = min(valley, prices[i]);
            f[i] = max(f[i - 1], prices[i] - valley);
        }
        for (int i = prices.size() - 2, peak = prices[prices.size() - 1]; i >= 0; --i) {
            peak = max(peak, prices[i]);
            g[i] = max(g[i], peak - prices[i]);
        }
        int max_profit = 0;
        for (int i = 0; i < prices.size(); ++i)
            max_profit = max(max_profit, f[i] + g[i]);
        return max_profit;
    }

阅读(614) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~