【Leetcode 53】最大子序和

本文主要是介绍【Leetcode 53】最大子序和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

方法一：采用贪心法，判断每次和是否大于0

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;for(int num: nums) {if(sum > 0) {sum += num;} else {sum = num;}ans = Math.max(ans, sum);}return ans;}
}

方法一的变种，采用动态规划

class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}

方法二：分治法

https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/

参考链接
https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/

https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/

这篇关于【Leetcode 53】最大子序和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---