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

最大子序列的和_子序列和最大值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)


相关推荐

  • C#MQTTNET客户端使用说明

    C#MQTTNET客户端使用说明C#MQTTNET客户端使用说明1.如何使用1.我想启动MQTT客户端,我该怎么做?2.我想收到服务器发来消息,我该怎么做?3.我想知道客户端是否连接成功,我该怎么做?3.我想知道怎样重连服务器,我该怎么做?1.如何使用1.我想启动MQTT客户端,我该怎么做?try{IMqttClientclient=newMqttFactory().CreateMqttClient();varbuild=newMqttClientOptionsBuilder()//配

  • MessageDigest简要

    MessageDigest简要本文博客原參考文章:http://blog.sina.com.cn/s/blog_4f36423201000c1e.html一、概述java.security.MessageDigest类用于为应用程序提供信息摘要算法的功能,如MD5或SHA算法。简单点说就是用于生成散列码。信息摘要是安全的单向哈希函数,它接收随意大小的数据。输出固定长度的哈希值。关…

  • sql smallint与int_datetime数据类型

    sql smallint与int_datetime数据类型使用整数数据的精确数字数据类型。bigint数值范围从-2^63(-9223372036854775808)到2^63-1(9223372036854775807)的整型数据(所有数字)。存储大小为8个字节。int数值范围从-2^31(-2,147,483,648)到2^31-1(2,147,483,647)的整型数据(所有数字)。存储大小为4个字节。int的SQL-92同义字为integer。smallint数值范围从-2^15(-32,76

  • mysql usegeneratedkeys_Mybatis Generator insert useGeneratedKeys keyProperty[通俗易懂]

    mysql usegeneratedkeys_Mybatis Generator insert useGeneratedKeys keyProperty[通俗易懂]Mybatis自动生成代码,需要用到mybatisGenerator,详见http://mybatis.github.io/generator/configreference/generatedKey.htmlinsert语句如果要返回自动生成的key值,一般会在insert里加入useGeneratedKeys属性,例如insertintosubtasks(SID,TID,RID,S…

  • 预制发票,相关屏幕增强及bapi 增强

    预制发票,相关屏幕增强及bapi 增强MIRO:需要对屏幕增强,实现可以输入xref1,xref2.如下图:图中,参考代码1和参考代码2都是通过隐式增强放出来的,具体操作过程请查看链接:https://blogs.sap.com/2020/11/04/xref1-xref2-xref3-in-miro-the-ultimate-solution/在下列程序中,写隐式增强相关表增强:之所以在这么多表中增强,是为了后面过账的时候,能把参考码传递给财务凭证2.上面…

  • 冰河凭什么能够顺利拿下三个软考高级证书?有什么技巧(诀窍)吗?[通俗易懂]

    冰河凭什么能够顺利拿下三个软考高级证书?有什么技巧(诀窍)吗?[通俗易懂]最近很多读者问冰河:冰河,你是如何拿下三个软考高级证书的?有什么诀窍吗?今天我们先简单聊聊冰河考了哪些软考高级证书,后面给大家分享软考技巧!

发表回复

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

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