題目描述
有n個(gè)硬幣排成一排箫措，每次要你從最左邊或者最右側(cè)拿出一個(gè)硬幣寂曹“テ總共拿k次。寫一個(gè)算法稀颁，使能拿到的硬幣的和最大芬失。
思路點(diǎn)撥
將list的前綴和求出來，然后依次枚舉右邊取x個(gè)匾灶，那么剩下就是左邊去k - x個(gè)棱烂，用前綴和可以O(shè)(1)算出答案，所以整體復(fù)雜度為O(n)阶女。
考點(diǎn)分析
想清楚后可以發(fā)現(xiàn)不管每次從左邊還是右邊拿颊糜，最后從左邊拿的個(gè)數(shù)和從右邊拿的個(gè)數(shù)是確定的，那么我們可以通過雙指針或者前綴和+掃描線的方式進(jìn)行枚舉左右拿硬幣的個(gè)數(shù)秃踩，這樣就可以O(shè)(n)的復(fù)雜度優(yōu)美的過這題了衬鱼。
參考程序
https://www.jiuzhang.com/solution/take-coins/
image
