[LintCode] 150 Best Time to Buy and Sell Stock II 解题报告

Description
Say you have an array for which the i^th 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).



Example
Given an example [2,1,2,0,1], return 2



思路
可以无限次买卖，那么我们从左往右遍历数组，只要发现股价有波动（前一天的价格比今天的低），我们就在前一天买，今天卖。
遍历完数组以后，获利的总和，就是在可以无限买卖的情况下获得的最大利润。



Code

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                int thisProfit = prices[i] - prices[i - 1];
                maxProfit += thisProfit;
            }
        }
        
        return maxProfit;
    }
};