首页 > 其他分享 >01-最大子列和问题

01-最大子列和问题

时间:2022-09-19 20:01:19浏览次数:73  
标签:01 return 子列 int curSum length maxSum 最大

最大子列和问题

概述

本文主要讲解最大子列和问题的求解
什么是最大子列和问题?有一个整数数组{A1, A2,A3,...,An}
求函数f(i,j)=max(0,∑Ak), k∈[i,j] 的值
简单来说,求一个数组所有子序列中和最大的子序列的和的值

方法

简单来说有四种解决方法,分别为三重循环,二重循环,分治法,单循环

package com.kuang.example01;

/**
 * 求最大子列的和
 * 最大子列和问题,有一个整数序列{A1,A2,A3,A4...An}
 * 求f(i,j)=max{0, ∑Ak} k从i取到j
 * 简单来说就是求一个序列的最大的子列和
 *
 * @since 2022-09-19
 */
public class MaxSumOfSubSequence {

    /**
     * 使用三重循环 时间复杂度O(n^3)
     *
     * @param a
     * @return
     */
    public int threeFor(int[] a){
        int curSum = 0;
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                curSum = 0;
                for (int k = i; k <j ; k++) {
                    curSum += a[k];
                }
                if(curSum>maxSum){
                    maxSum = curSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 使用二重循环 时间复杂度O(n^2)
     *
     * @param a
     * @return
     */
    public int twoFor(int[] a){
        int curSum = 0;
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            curSum = 0;
            for (int j = i; j < a.length; j++) {
                curSum += a[j];
                if(curSum>maxSum){
                    maxSum = curSum;
                }
            }
        }
        return maxSum;
    }

    /**
     * 使用分治法 时间复杂度O(nlog(n))
     *
     * @param a
     * @return
     */
    public int divideAndConquer(int[] a){
        // 分治写不出来,以后再写
        return 0;
    }

    /**
     * 使用单循环 时间复杂度O(n)
     *
     * @param a
     * @return
     */
    public int oneFor(int[] a){
        int curSum = 0;
        int maxSum = 0;
        for (int i = 0; i < a.length; i++) {
            curSum += a[i];
            if (curSum>maxSum){
                maxSum = curSum;
            }
            if(curSum<0){
                curSum =0;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] a = {-1,3,-2,4,-6,1,6,-1}; //正确结果应该是7
        MaxSumOfSubSequence sum = new MaxSumOfSubSequence();
        int result = sum.oneFor(a);
        System.out.println(result);

        int[] a1 = {4,-3,5,-2,-1,2,6,-2}; //正确结果应该是11
        int result1 = sum.oneFor(a1);
        System.out.println(result1);
    }
}

标签:01,return,子列,int,curSum,length,maxSum,最大
From: https://www.cnblogs.com/Oh-mydream/p/16708839.html

相关文章

  • 01-物体检测方法概述
    1.物体检测的派系2.传统方法 3.基于锚框的物体检测算法4.无需锚框的物体检测算法 5.物体检测常用数据集   5.1通用物体检测数据集    ......
  • 把秒数转化成时间格式(12小时制)比如输入:3612 , 输出为 AM 01:00:12 比如输入:75612 , 输
    #include<stdio.h> main() {   inta;   scanf("%d",&a);   if(a<43199)   {     inth;   h=a/3600;   intm;   m=(a%3600)/60;......
  • 解决苹果钥匙串-34018错误: A required entitlement isn't present.
        最近破解了一个苹果版本关键软件,在跳过各种检测延长试用时间之后发现无法保存钥匙串数据了。调试后发现SecItemAdd无法添加钥匙串,返回值-34018,搜寻后发现是因......
  • 肖sir__Scratch基本介绍__01
    Scratch简介   走近Scratch,让孩子走在时代潮流的前列,赶上物联网智能化趋势。希望每个孩子能在编程中获得乐趣,喜欢上编程,懂编程。在编程中培养孩子们的思考能力和逻辑......
  • Spring基础 01
    Maven项目的创建项目所在路径-项目一-创建Module-添加Webapp(ProjectStructure)-项目二Spring简介分层全栈(各层解决方案)轻量级框......
  • VeighNa进阶EP01:TuShare数据源接入
    前言上次我们介绍了一下vnpy量化框架的搭建,今天我们来说说TuShare数据源的接入。因为公司之前一直是从一些金融网站或者证券服务商获取的,公司最近决定改变策略通过TuShare......
  • T1010: 计算分数的浮点数值(信息学一本通C++)
    [题目描述]两个整数a和b分别作为分子和分母,既分数a/b,求它的浮点数值(双精度浮点数,保留小数点后9位)。[输入]输入仅一行,包括两个整数a和b。[输出]输出也仅一行,分数......
  • T1012: 计算多项式的值(信息学一本通C++)
    [题目描述]对于多项式f(x)=ax3+bx2+cx+d和给定的a,b,c,d,x,计算f(x)的值,保留到小数点后7位。[输入]输入仅一行,包含5个实数,分别是x,及参数a、b、c、d的值,每个数都是绝对值......
  • T1011: 甲流疫情死亡率(信息学一本通C++)
    [题目描述]甲流并不可怕,在中国,它的死亡率并不是很高。请根据截止2009年12月22日各省报告的甲流确诊数和死亡数,计算甲流在各省的死亡率。[输入]输入仅一行,有两个整数,第一......
  • Problem P18. [算法课贪婪]6和9组成的最大数字
    贪心:把9换成6是不可能的,只有把6换成9,而且要换就换最高位的那个6C++:to_string可以将整数转化为string类型,stoi可以将string转化为int类型,这个好用!#i......