首页 > 基础算法 > 贪心 > LeetCode-Best Time to Buy and Sell Stock II[贪心]
2014
11-18

LeetCode-Best Time to Buy and Sell Stock II[贪心]

Best Time to Buy 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).

标签: Array Greedy
分析

贪心法,低进高出,把所有正的价格差价相加起来。

把原始价格序列变成差分序列,本题也可以做是最大$m$子段和,$m=$数组长度。

代码1

// LeetCode, Best Time to Buy and Sell Stock II
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            int diff = prices[i] - prices[i - 1];
            if (diff > 0) sum += diff;
        }
        return sum;
    }
};

Java代码:

public class Solution {
    public int maxProfit(int[] prices) {
      if(prices.length == 0) return 0;
      int ans = 0;
      for(int i=1; i<prices.length; i++){
          if(prices[i] > prices[i-1])
            ans += prices[i]-prices[i-1];
      }
      return ans;
    }
}

相关题目
Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock III


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。