leetcode oj java 53. Maximum Subarray

本文主要是介绍leetcode oj java 53. Maximum Subarray，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、问题描述：

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

二、解决思路：

在加法计算中如果前边的sum<0,必然会使得后边的和减少，抛弃。

当遇到一个负数的时候，不能简单的丢弃，还要判断它前边的max(sum).

过程： 遍历整个数组，变量sum 和max 分别记录当前位置的可能最大值和当前位置之前的最大值，当遇到一个负数的时候，max更新为改负数之前的最大值，

如果sum 小于0的话，置为0表示又要重新开始计数。最后取sum之前的max 和sum中最大值。

三、代码：

public class Solution {public int maxSubArray(int[] nums) {int re = nums[0];if (nums.length == 1) {return nums[0];}int sum = re;int max = re;for (int i = 1; i < nums.length; i++) {if (nums[i] < 0) {max = max > sum ? max : sum;}if (sum < 0) {sum = 0;}sum += nums[i];}max = max > sum ? max : sum;return max;}
}

beat 72.3%

这篇关于leetcode oj java 53. Maximum Subarray的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---