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

// 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;
}
}

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。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。