[leetcode in golang]121、买卖股票的最佳时机

动态规划

暴力法（多次遍历）

func maxProfit(prices []int) int {
    maxprofit:=0
    for i:=0;i<len(prices)-1;i++{
        for j:=i+1;j<len(prices);j++{
            if prices[j]-prices[i]>maxprofit{
                maxprofit=prices[j]-prices[i]
            }
        } 
    }
    return maxprofit
}

时间复杂度：O(n^2）循环运行[n(n−1)]/2次。

空间复杂度：O(1)。

第一次提交的错误是两个for loop的终止条件相反了……怎么想的，明明j跑在i前面

一次遍历

func maxProfit(prices []int) int {
    maxprofit:=0
    minprice:=math.MaxInt32
    for i:=0;i<len(prices);i++{
        if prices[i]<minprice{
            minprice=prices[i]
        }
        if prices[i]-minprice>maxprofit{
            maxprofit=prices[i]-minprice
        }
    }
    return maxprofit
}

时间复杂度：O(n)

空间复杂度：O(1)

这个方法和上面方法的区别在于：定义一个最小值的变量为整数最大值，在第一次遍历中，一边遍历，一边更新最小值；更新最小值的同时也可以更新最大利益值。
上一个方法中：没有定义最小值，固定数组中一个元素，与其后每一个元素逐一比较，每一次比较都要计算两个元素之间的差值，更新最大利益值。

有疑问加站长微信联系（非本文作者）