最大子序列的和_子序列和最大值

最大子序列的和_子序列和最大值53. 最大子序和

大家好,又见面了,我是你们的朋友全栈君。

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账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号