找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1181|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Best Time to Buy and Sell Stock II】【刷题第一弹】

[复制链接]

11

主题

8

精华

253

积分

高级会员

Rank: 3Rank: 3

积分
253
发表于 10-12-2014 12:45 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 TeamEditor 于 11-19-2014 10:36 AM 编辑

leetcode通道:
http://oj.leetcode.com/problems/ ... -and-sell-stock-ii/

题目:

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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

思路 :brutal force 的思路是在上升区间最开始买入,在结束时卖出,可以滑动窗口做,实现起来比较麻烦。简化之。由于可以在卖了手上股票之后马上购买,所以只要股票存在涨幅,就进行买卖操作,即可获得最大利益。举例: 1,2,3,4。1买,2卖,2再买,3卖,3再买,4卖,这样获得的总收益与1买,4卖的收益是一样的。

代码:
  1. public int maxProfit(int[] prices) {
  2.         int prof = 0;
  3.         for (int i = 1; i < prices.length; i++) {
  4.             if (prices[i] > prices[i - 1]) prof += prices[i] - prices[i - 1];
  5.         }
  6.         return prof;
  7.     }
复制代码




建议的回复格式:
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目: (选填)

本帖被以下淘专辑推荐:

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 11-17-2014 08:41 PM | 显示全部楼层
另一种思路:当股票价格处于增长状态时,不计算,当股票价格变低时,计算一次,并更新当前的最低股票价格为当前价格。如果从某天开始到最后一天,股票价格一直上涨,那就少算了一次,所有需要增加股票为零的一天
  1.     int maxProfit(vector<int> &prices) {
  2.         prices.push_back(0);
  3.         
  4.         int profits = 0;
  5.         int min_price = prices[0];
  6.         
  7.         for(int i = 1; i < prices.size(); i++){
  8.             if(prices[i] < prices[i - 1]){
  9.                 profits += (prices[i - 1] - min_price);
  10.                 min_price = prices[i];
  11.             }
  12.         }
  13.         
  14.         return profits;
  15.         //return profits + (prices[prices.size() - 1] - min_price);,不加一天的收益计算
  16.     }
复制代码

这种思路避免了每次都累加收益,但是股票价格下降时则需要每次计算,平均的总体计算量和lz的思路应该相同。
期待大神写出只需要计算峰值和谷值的代码
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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