大家好,又见面了,我是你们的朋友全栈君。
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 取三个中的最大
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107354.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...