Problem

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

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

思路

• 暴力解法:

  • 遍历数组的时候, 只要当前元素与它之前元素中的最小值的差大于0, 加进profit中
  • O(n ^ 2) time
  • 上面这个暴力解法其实是错的. 正正是因为通过这个错的暴力解法, 优化的方案也出错了.

• 一开始解题的时候不要总想着有一个index从左往右走, 然后干些什么.

  • 最开始解题的idea应该是给你一个小例子, 你如何最直接得到答案. 然后去想要这样得到答案需要些什么?

• 因而发现, 只要是升序的都加进profit中.

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }

        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }
        return profit;
    }