121. 買賣股票的最佳時機

給定一個數組?prices?，它的第?i?個元素?prices[i]?表示一支給定股票第?i?天的價格。

你只能選擇?某一天?買入這只股票，并選擇在?未來的某一個不同的日子?賣出該股票。設計一個算法來計算你所能獲取的最大利潤。

返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤，返回?0?。

示例 1：

輸入：[7,1,5,3,6,4]
輸出：5
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

示例 2：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 沒有交易完成, 所以最大利潤為 0。

思路：由于只能買入賣出各一次，使用max來記錄盈利profit就好了。一開始先用一個超出題目給出范圍的很大的數來表示不買入（Java中有BigInteger這個類）。

代碼實現：

class Solution {
public:int maxProfit(vector<int>& prices) {int in = 100000;int profit = 0;for(const int& out : prices) {profit = max(out - in, profit);in = min(in, out);}return profit > 0 ? profit : 0;}
};

122. 買賣股票的最佳時機II

給你一個整數數組?prices?，其中?prices[i]?表示某支股票第?i?天的價格。

在每一天，你可以決定是否購買和/或出售股票。你在任何時候?最多?只能持有?一股?股票。你也可以先購買，然后在?同一天?出售。

返回?你能獲得的?最大?利潤?。

示例 1：

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 。總利潤為 4 + 3 = 7 。

示例 2：

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 。總利潤為 4 。

示例?3：

輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這種情況下, 交易無法獲得正利潤，所以不參與交易可以獲得最大利潤，最大利潤為 0 。

思路：在最后一天股票收盤之前，都可以交易，中間也可以多次交易。所以，只收集正利潤的交易即可。

代碼實現：

class Solution {
public:int maxProfit(vector<int>& prices) {int ret = 0;for(int i = 1; i < prices.size(); ++i) {int profit = prices[i] - prices[i - 1];ret += max(profit, 0);}return ret;}
};

55. 跳躍游戲

給你一個非負整數數組?nums?，你最初位于數組的?第一個下標?。數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標，如果可以，返回?true?；否則，返回?false?。

示例?1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

示例?2：

輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

思路：每次總是在局部最優的范圍內找下一個局部最優，最后判定是否能夠跳到最后一個下標。

代碼實現：

class Solution {
public:bool canJump(vector<int>& nums) {if(nums.size() == 1) return true;int cover = 0;for(int i = 0; i <= cover; ++i) {cover = max(cover, i + nums[i]);if(cover >= nums.size() - 1) return true;}return false;}
};

45. 跳躍游戲II

給定一個長度為?n?的?0 索引整數數組?nums。初始位置為?nums[0]。

每個元素?nums[i]?表示從索引?i?向前跳轉的最大長度。換句話說，如果你在?nums[i]?處，你可以跳轉到任意?nums[i + j]?處:

• 0 <= j <= nums[i]?
• i + j < n

返回到達?nums[n - 1]?的最小跳躍次數。生成的測試用例可以到達?nums[n - 1]。

示例 1:

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是 2。從下標為 0 跳到下標為 1 的位置，跳?1 步，然后跳?3
步到達數組的最后一個位置。

示例 2:

輸入: nums = [2,3,0,1,4]
輸出: 2

思路：題目告訴我們所有的情況都是可以跳到最后一個下標的，只需要我們判斷怎樣的跳數最少，那么，依舊需要一個當前下標能跳到的最遠距離，并用一個nextIndex來記錄在當前范圍內能夠跳得最遠的下一個下標（下次就跳過去），每當到達當前范圍的邊界，return值（跳數）就需要加一了。

代碼實現：

class Solution {
public:int jump(vector<int>& nums) {int curIndex = 0;int ret = 0;int nextIndex = 0;for(int i = 0; i < nums.size() - 1; ++i) {nextIndex = max(i + nums[i], nextIndex);if(curIndex == i) {curIndex = nextIndex;++ret;}}return ret;}
};

1005. K次取反后最大化的數組和

給你一個整數數組?nums?和一個整數?k?，按以下方法修改該數組：選擇某個下標?i?并將?nums[i]?替換為?-nums[i]?。

重復這個過程恰好?k?次。可以多次選擇同一個下標?i?。以這種方式修改數組后，返回數組?可能的最大和?。

示例 1：

輸入：nums = [4,2,3], k = 1
輸出：5
解釋：選擇下標 1 ，nums 變為 [4,-2,3] 。

示例 2：

輸入：nums = [3,-1,0,2], k = 3
輸出：6
解釋：選擇下標 (1, 2, 2) ，nums 變為 [3,1,0,2] 。

示例 3：

輸入：nums = [2,-3,-1,5,-4], k = 2
輸出：13
解釋：選擇下標 (1, 4) ，nums 變為 [2,3,-1,5,4] 。

思路：因為一個數字可以重復用來取反，那么我們的解題思路就是盡可能把所有的負數都取反成為正數。要想實現這個，可以首先用sort對所有數的絕對值排序（因為不用返回下標），再通過遍歷來維護每一個數，當所有的負數都被取反為之后，就需要對絕對值最小的數取反了（以確保減去的數是最小的）。sort的規則（函數）寫成一個單獨的函數或者lambda表達式均可。

代碼實現：

class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {int ret = 0;sort(nums.begin(), nums.end(), [](int a, int b)->{return abs(a) > abs(b);});for(int i = 0; i < nums.size() - 1; ++i) {if(nums[i] < 0 && k > 0) {nums[i] *= -1;--k;}}if(k % 2 == 1) {nums[nums.size() - 1] *= -1;}for(const auto& num : nums) {ret += num;}return ret;}
};