1.最大子序和
給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子陣列 [4,-1,2,1] 的和最大，為 6，
進階:
如果你已經實作復雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
代碼實作：
1.采用動態規劃解法
思路：
? 動態規劃的本質：改變陣列元素，最后陣列中數值最大的即為題解，
? 倘若前一項<=0，則陣列當前值不變；倘若>0，則將當前項加至sum中；最后取最大值
class Solution {
public int maxSubArray(int[] nums) {
// 動態規劃解法：
int ans = nums[0]; // 最大和
int sum = 0; // 單項和
for (int i=0;i<nums.length;i++) {
if(sum > 0){
sum += nums[i];
}else {
sum = nums[i];
}
ans = Math.max(ans,sum);
}
return ans;
}
}
2.采用貪心解法
思路：
? 貪心演算法的本質：當前一項 < 0時，舍去前面所有加和，賦值為0；否則，進行加和操作，然后與最大值進行比較，最侄訓傳最大值！
? 與動態規劃不同的一點是：此方法不需要改變陣列內的數值，單純提取最大值
class Solution {
public int maxSubArray(int[] nums) {
// 貪心解法
int ans = 0;
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
ans += nums[i];
max = Math.max(max,ans);
if (ans < 0){
ans = 0;
}
}
return max;
}
}
2.加一
給定一個由整陣列成的非空陣列所表示的非負整數，在該數的基礎上加一，
最高位數字存放在陣列的首位， 陣列中每個元素只存盤單個數字，
你可以假設除了整數 0 之外，這個整數不會以零開頭，
示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入陣串列示數字 123，
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入陣串列示數字 4321，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/plus-one
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143261.html
標籤：其他