[leetcode]Best Time to Buy and Sell StockII

新博文：[leetcode]Best Time to Buy and Sell Stock II

http://oj.leetcode.com/problems/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).

 其实这道题相比于第一题http://huntfor.iteye.com/blog/2051366来讲，想法反而简单了

题中大意为，可以进行多次买入卖出，求最大收益，显然，我们只要把每一个增区间的极大值与极小值的差求出来，再将这些差值全部加起来就是了，因此现在题目的重点就变成了如何判断哪些点是极值点，我用的是比较偷懒的办法，维护三个指针，pre，post分别指向前后节点。通过比较前后节点的值与当前节点的值，就可以判断当前节点是否是极值点。

 

    public int maxProfit(int[] prices) {
		int pre = 0;
		int post = 1;
		int buy = 0;//买入点
		int profit = 0;//收益
		if(prices == null || prices.length == 1 || (prices.length == 2 && prices[0] >= prices[1])){
			return 0;
		}
		for(int tem = 0; tem < prices.length ; tem++,pre = tem - 1,post = tem + 1){
			if(post < prices.length && prices[tem] <= prices[pre] && prices[tem] < prices[post]){
				buy = prices[tem];
			}
			if( ( post < prices.length && prices[tem] > prices[pre] && prices[tem] >= prices[post]) || (post == prices.length && prices[tem] > prices[pre])){
				profit += prices[tem] - buy;
			}
		}
		return profit;
	
    }