九章演算法 | Google 面試題：Take Coins

來自專欄九章演算法 - lintcode/leetcode題解

撰文 | JZ

專欄 | 九章演算法

題目描述

有n個硬幣排成一排，每次要你從最左邊或者最右側拿出一個硬幣。總共拿k次。寫一個演算法，使能拿到的硬幣的和最大。

思路點撥

將list的前綴和求出來，然後依次枚舉右邊取x個，那麼剩下就是左邊去k - x個，用前綴和可以O(1)算出答案，所以整體複雜度為O(n)。

考點分析

想清楚後可以發現不管每次從左邊還是右邊拿，最後從左邊拿的個數和從右邊拿的個數是確定的，那麼我們可以通過雙指針或者前綴和+掃描線的方式進行枚舉左右拿硬幣的個數，這樣就可以O(n)的複雜度優美的過這題了。

九章參考程序

https://www.jiuzhang.com/solution/take-coins/

推薦閱讀：