題目內容
給定一個整數陣列 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提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105進階：如果你已經實作復雜度為 O(n) 的解法，嘗試使用更為精妙的 分治法 求解，
題解
class Solution { public int maxSubArray(int[] nums) { int sum = 0; int ans = nums[0]; for(int num:nums){ if(sum>0){ sum+=num; }else{ sum = num; } ans = Math.max(ans,sum); } return ans; } }
解題思路
- 首先明確一個概念，求最大子序列，就不能對該陣列進行排序
- 其次要明確的是，對于這種求最大子序列問題，使用動態規劃是最佳的解決方案
- 動態規劃的首先對陣列進行遍歷，當前最大連續子序列和為sum，結果為ans
- 如果sum>0,則說明sum對結果有增益效果，則sum保留并加上當前遍歷數字
- 如果sum<=0,則說明sum對結果無增益效果，需要舍棄，則sum直接更新為當前遍歷數字
- 每次比較sum和ans的大小，將最大值置為ans,遍歷結束回傳結果
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298263.html
標籤：其他
下一篇：關于API網關（三）權限