題目原址

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

題目描述

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example2:

Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.

解題思路

翻譯：
你有一個數組，數組中的數是當天的股票價格，如prices[1] = 10，表示第2天的股票價格為10
你最多有一次交易的機會（即：只能買一次股票，賣一次股票）設計一個算法找出交易的最大利潤。

• 這道題使用Kadane’s algorithm(Kadane算法)實現，Kadane是卡內基梅隆大學的教授，而該算法是為了解決最大子序列的和（maximum subarray）提出的。
• Leetcode上面有很多求最大子序列和的問題，這種題應該算是一個類型的。
• 解決該題的方法還是很簡單的：
  
  • 判斷當當前最大利益 + 當前的元素-當前元素的前一個元素的值是否是負數，如果是負數，就說明已經賠沒了，不能買當前股票的前面的股票了，所以當前的利益為0。如果值為正數，則還可以往下遍歷。
  • 每次更改當前利益之后，都要判斷當前利益與總利益之間的大小，保證總利益永遠最大。

AC代碼

class Solution {public int maxProfit(int[] prices) {int max_ending_here = 0;int max_so_far = 0;for(int i = 1; i < prices.length; i++) {max_ending_here = Math.max(0, prices[i] - prices[i-1] + max_ending_here);max_so_far = Math.max(max_so_far, max_ending_here);}return max_so_far; } }

感謝

https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input/3

總結

以上是生活随笔為你收集整理的Leetcode——121. Best Time to Buy and Sell Stock的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。