懒人读算法(五)-求最大子数组

本文主要是介绍懒人读算法(五)-求最大子数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

趣味题

给一个数组，求最大的连续子数组的和
如数组:[-2,1,-3,4,-1,2,1,-5,4]
则最大的连续子数组[4,-1,2,1] 和为6

答案:

public class Solution {public int maxSubArray(int[] nums) {int[] dp = new int[nums.length];dp[0] = nums[0];int max = dp[0];for(int i = 1; i < nums.length; i++) {dp[i] = nums[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);//当前的最大值=当前数+之前最大值(如果是负数则为0)max = Math.max(dp[i], max);//当前相加的最大值和之前最大值比较}return max;}}

核心思路:
遍历整个数组，把数字相加的和放在dp里，如果dp的前一个值为负数，则从0开始继续加。每一次遍历都记录下最大值

这篇关于懒人读算法(五)-求最大子数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---