大家好，又见面了，我是你们的朋友全栈君。
53. 最大子序和
https://leetcode-cn.com/problems/maximum-subarray/description/
package com.test; import java.util.ArrayList; import java.util.List; /** * @Author stono * @Date 2018/8/21 上午10:56 */ public class Lesson053 { public static void main(String[] args) { //int[] nums = {-2,1,-3,4,-1,2,1,-5,4}; int[] nums = {-2,-1}; int max = maxSubArray(nums); System.out.println(max); } public static int maxSubArray(int[] nums) { // 存放最大序列和 int max = 0; int sum = 0; for (int i = 0; i < nums.length; i++) { int num = nums[i]; // 如果num出现负值，序列和就会下降，先存一份序列和 if(num<0 && i>0){ max = sum>max?sum:max; } // 第一个值就小于0，先把第一个值存起来 if (num < 0 && i == 0) { max = num; } // 如果序列和小于0，就清空一下重新开始累加； if (sum < 0) { sum = 0; } sum = sum + num; // 每次判断一下，存储最大max max = sum>max?sum:max; } return max; } }
还是有别的方法：
仿python的java：
class Solution { public int maxSubArray(int[] nums) { // 最大值 int max = nums[0]; // 最大值缓存列表 List<Integer> maxList = new ArrayList<>(8); // 先把第一个值加进入 maxList.add(max); for (int i = 1; i < nums.length; i++) { // 再依次往里面加值 maxList.add(nums[i]); // 如果之前的那个值大于0，就进行累加 if (maxList.get(i-1) > 0) { maxList.set(i , maxList.get(i) + maxList.get(i - 1)); } // 如果累加的结果大于max，就更换max的值 if (maxList.get(i) > max) { max = maxList.get(i); } } return max; } }
动态规划：
转移条件是 逐项求和以后如果没有变大就重新开始
已通过
分治：
1 分成两部分，计算左边，右边和中间(包含中间元素的连续子集)的最大值
2 取三个中的最大
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/107354.html原文链接：https://javaforall.net
![在线快速将pdf转换成word[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
