原題目鏈接：53. 最大子序和
題目描述：
給定一個整數陣列 nums ，找到一個具有最大和的連續子陣列（子陣列最少包含一個元素），回傳其最大和，
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續子陣列 [4,-1,2,1] 的和最大，為 6 ，
示例 2：
輸入：nums = [1]
輸出：1
示例 3：
輸入：nums = [0]
輸出：0
示例 4：
輸入：nums = [-1]
輸出：-1
示例 5：
輸入：nums = [-100000]
輸出：-100000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
做題思路：
- 其實這道題可以這么想，我們以nums = [-2，3，-1，1，-3] 為例子，首先要對陣列進行遍歷，當前最大連續子序列和為 sum，結果為 ans
1.1 如果 sum <= 0，則說明 sum 對結果無增益效果，需要舍棄，則 sum 直接更新為當前遍歷數字，也就是說假如全是負數，那就是找最大值即可，因為負數肯定越加越大，
1.2 如果 sum > 0，則說明 sum 對結果有增益效果，則 sum 保留并加上當前遍歷數字，也就是說如果有正數，則肯定從正數開始計算和，不然前面有負值，和肯定變小了，所以從正數開始，
1.3 當和小于零時，這個區間就告一段落了，然后從下一個正數或者是最小的負數重新開始計算，
1.4 每次比較 sum 和 ans的大小，將最大值置為ans，遍歷結束回傳結果
廢話不多說，直接上代碼，為了讓各位看官更能清晰理解，我的代碼寫得不精簡，我的代碼里加了大量的注釋，相信各位看官可以理解，如果我有些沒寫清楚或者寫錯的，可以評論區或者私信我喔
public int maxSubArray(int[] nums) {
//連續的幾個元素加起來的和
int sum = 0;
//假設陣列只有一個元素，就取出第一個元素
int ans = nums[0];
//遍歷陣列
for(int num : nums){
if(sum > 0){ //如果sum大于0，說明要加上遍歷的元素，因為sum是正數
sum += num;
}else{ //如果sum是小于0的，直接等于遍歷到的元素就行了，反正sum已經是負數了
sum = num;
}
//Math類的max方法是回傳兩個資料中的最大的資料
//例如(1,2)回傳2，(2,4)回傳4
//用ans和sum進行比較，這樣做的目的是
//即使下一位元素是負數，那我們已經把之前的最大值賦值給ans，所以不用怕
ans = Math.max(ans,sum);
}
//回傳最大值
return ans;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/258993.html
標籤：其他
上一篇：golang日志和配置設計