大家好,又见面了,我是你们的朋友全栈君。
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.cn/107354.html原文链接:https://javaforall.cn