題目

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

題目大意

假設(shè)有一個(gè)數(shù)組，它的第i個(gè)元素是一個(gè)給定的股票在第i天的價(jià)格。設(shè)計(jì)一個(gè)算法來找到最大的利潤。你可以完成盡可能多的交易(多次買賣股票)。然而,你不能同時(shí)參與多個(gè)交易(你必須在再次購買前出售股票)。
給出一個(gè)數(shù)組樣例[2,1,2,0,1], 返回 2

解題思路

本題由于是可以操作任意次數(shù)，只為獲得最大收益，而且對于一個(gè)上升子序列，比如：[5, 1, 2, 3, 4]中的1, 2, 3, 4序列來說，對于兩種操作方案：
1 在1買入，4賣出
2 在1買入，2賣出同時(shí)買入，3賣出同時(shí)買入，4賣出
這兩種操作下，收益是一樣的。
所以可以從頭到尾掃描prices，如果price[i] – price[i-1]大于零則計(jì)入最后的收益中。即貪心法

代碼

func maxProfit(prices []int) int {
    len1 := len(prices)

    var sum int

    for i := 1; i < len1; i++{
        if prices[i] > prices[i-1] {
            sum += prices[i] - prices[i-1]
        }

    }

    return sum
}