最大连续子串

末蓝、 2024-04-17 21:11 85阅读 0赞

问题描述：

给定一个由数字组成的数组，求出和最大的子数组

求解方法：

1.暴力法

选取所有连续和的可能性，O(n^2)

2.分析法

当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。

3.动态规划

记s\[i\]是以a\[i\]结尾的最大子数组和

s\[i+1\]=max(s\[i\]+a\[i+1\],a\[i+1\])

s\[0\]=a\[0\];

遍历数组a\[i\]即可得到以每一项结尾的最大子数组和s\[i\],求出其中最大值

package offer_0831;
    
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.List;
    
    public class MaxSerialSubList {
        // 暴力法 - func1 - 略
        
        // 分析法
        Integer func2(List<Integer> nums) {
            int maxRes = 0;
            int resBefore = 0;
            for (Integer i : nums) {
                if (resBefore < 0) {
                    resBefore = i;
                } else {
                    resBefore = i + resBefore;
                    maxRes = maxRes > resBefore ? maxRes : resBefore;
                }
            }
            return maxRes;
        }
    
        // 动态规划
        Integer func3(List<Integer> nums) {
            List<Integer> res = new LinkedList<Integer>();
            res.add(nums.get(0));
            for(int i = 1;i< nums.size();i++){
                res.set(i,res.get(i-1)+nums.get(i)>0?res.get(i-1)+nums.get(i):nums.get(i));
            }
            return  Collections.max(res);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，85人围观）

还没有评论，来说两句吧...

相关阅读

相关最大连续子串

题描述：给定一个由数字组成的数组，求出和最大的子数组求解方法： 1.暴力法选取所有连续和的可能性，O(n^2) 2.分析法当遍历到第i个元素时，判断在...

末蓝、/ 2024年04月17日 21:11/ 0 赞/ 86 阅读

相关最大连续和（子串）

了4种方法实现： include<bits/stdc++.h> using namespace std; typedef long long l...

青旅半醒/ 2024年04月17日 05:22/ 0 赞/ 90 阅读

相关最长公共连续子串

给出两个字符串（可能包含空格）,找出其中最长的公共连续子串,输出其长度。输入描述: 输入为两行字符串（可能包含空格），长度均小于等于50. 输出描述:

谁借莪１个温暖的怀抱￠/ 2023年07月03日 07:23/ 0 赞/ 20 阅读

相关最大连续子序列

最大连续子序列：是指序列中所有子序列中元素和最大的一个例如\{-2,11，-4,13，-5.-2\}中最大连续子序列为\{11，-4,13\}其和为20

雨点打透心脏的1/2处/ 2023年06月17日 10:51/ 0 赞/ 24 阅读

相关最长连续无重复子串

代码一： -------------------- include <iostream> include <algorithm> using n

Dear 丶/ 2022年10月04日 12:53/ 0 赞/ 206 阅读

相关最长公共子串与最长连续子串算法

利用DP思想最长公共子串中result\[i\]\[j\]存放str1前i个与result\[j\]个的最长公共子串，当str1\[i + 1\]==str2\[j + 1

男娘i/ 2022年08月11日 16:44/ 0 赞/ 244 阅读

相关动态规划题目（三）——最大连续乘积子串

动态规划题目（三）——最大连续乘积子串 1. 题目描述给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大

绝地灬酷狼/ 2022年08月06日 01:27/ 0 赞/ 267 阅读

相关最大连续子序列

最大连续子序列 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

淡淡的烟草味﹌/ 2022年08月05日 13:20/ 0 赞/ 221 阅读

相关字符串中连续最长重复子串

使用后缀数组的概念。 include <stdio.h> include <stdlib.h> include <string.h>

一时失言乱红尘/ 2022年05月30日 03:56/ 0 赞/ 227 阅读

相关最大连续子序列

[B - 最大连续子序列][B -] 给定K个整数的序列\{ N1, N2, ..., NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, ..., Nj

亦凉/ 2021年12月20日 04:27/ 0 赞/ 341 阅读