轻松搞定动态规划之最大子段和问题

布满荆棘的人生 2023-07-20 05:50 193阅读 0赞

*  【问题描述】  
    给定由n个整数组成的序列a1,a2,…,a(n),求该序列字段和的最大值。
 *  分析  
    当所有整数均为负值时定义其最大字段和为0。
 *  定义：  
    ![在这里插入图片描述][20200331170825753.png]  
    即0或者，序列i到序列j之和两者之间最大的值。
 *  例如：序列（-2，11，-4，13，-5，-2），求最大字段和为:  
    max=11+(-4)+13=20

#include<iostream>
    const int MAX_LEN =100;
    
    using namespace std;
    
    int getMaxSum(int* a,int n){ 
        int max=0;//假设最大值为0
        int temp=0;
        for(int i=0;i<n;i++){ 
            if(temp>0){ 
                temp+=a[i];//最大值临时变量只有大于零，才可能越加越大
            }else{ 
                temp=a[i];最大值临时变量只有小于零，直接等于a[i],否则越加越小
            }
            if(max<temp){ 
                max=temp;//判断赋值
            }
        }
        return max;
    }
    
    int main(){ 
        int a[MAX_LEN];
        int maxSum;
        int n;
    	cout<<"请输入序列的元素个数"<<endl;
        cin>>n;
    	cout<<"请依次输入序列的元素"<<endl;
        for(int i=0;i<n;i++){ 
            cin>>a[i];
        }
        maxSum=getMaxSum(a,n);
        cout<<maxSum<<endl;
    }

[20200331170825753.png]: /images/20230528/bcc2a399763246d4b811707e54286b83.png

发表评论取消回复

表情：

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

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

相关阅读

相关 C++动态规划------最大子段和的问题

目录最大子段和（动态规划C++）最大子段和的动态规划算法 4.4 最大子段和算法4.7计算最大子段和的动态规划算法算法4.8计算最大子段和的动态规划算法的

深藏阁楼爱情的钟/ 2024年03月22日 12:11/ 0 赞/ 162 阅读

相关最大子段和问题

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。例如, 当（a1,a2,a3,a4 ,a5,a6) = （-2,11

心已赠人/ 2023年10月05日 13:29/ 0 赞/ 118 阅读

相关轻松搞定动态规划之最大子段和问题

【问题描述】给定由n个整数组成的序列a1,a2,…,a(n),求该序列字段和的最大值。分析当所有整数均为负值时定义其最大字段和为0。

布满荆棘的人生/ 2023年07月20日 05:50/ 0 赞/ 194 阅读

相关轻松搞定动态规划解决矩阵连乘问题

【问题描述】给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的

浅浅的花香味﹌/ 2023年07月20日 05:40/ 0 赞/ 109 阅读

相关顺序表应用8：最大子段和之动态规划法

顺序表应用8：最大子段和之动态规划法 Time Limit: 5MS Memory Limit: 500KB [Submit][] [Statistic][] Pr

短命女/ 2022年09月26日 01:58/ 0 赞/ 163 阅读

相关 428-动态规划算法-最大子段和

题目如下 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nL

傷城~/ 2022年09月05日 04:27/ 0 赞/ 276 阅读

相关顺序表应用8：最大子段和之动态规划法

Problem Description 给定n(1<=n<=100000)个整数（可能为负数）组成的序列a\[1\],a\[2\],a\[3\],…,a\[n\],求该序

拼搏现实的明天。/ 2022年07月11日 13:19/ 0 赞/ 140 阅读

相关最大子段和动态规划实现

找到《最大子段和问题的动态规划求解》的pdf，讲解很透彻。 public class Main { public static void ma

偏执的太偏执、/ 2022年06月18日 11:08/ 0 赞/ 463 阅读

相关连续子段和问题（动态规划）

【问题描述】给出一段序列，选出其中连续且非空的一段使得这段和最大。【输入格式】输入文件的第一行是一个正整数 N，表示了序列的长度。第 2 行包含 N 个绝

冷不防/ 2022年06月08日 08:59/ 0 赞/ 280 阅读

相关动态规划之最小M段和问题

\include <stdio.h> \include <stdlib.h> \define MAX(a,b) a>b?a:b int a\[100\]; int

骑猪看日落/ 2022年04月22日 02:14/ 0 赞/ 554 阅读