动态规划１：状态转移方程-求最大子序列和

柔情只为你懂 2023-07-08 15:29 64阅读 0赞

时间复杂度Ｏ(n)  
序列：-2 11 -4 13 -5 -2

//最大连续子序列和
    //使用到状态转移方程
    #include <cstdio>
    #include "algorithm"
    using namespace std;
    const int maxn =10010;
    int A[maxn],dp[maxn];//A存放数字序列　　dp存放以A[i]结尾的连续序列最大和
    
    int main() { 
        int n;
        scanf("%d\d",&n);
        for(int i=0;i<n;i++)
        { 
            scanf("%d",&A[i]);
        }
        //边界
        dp[0]=A[0];
        for(int i=1;i<n;i++)
        { 
            //状态转移方程
            dp[i]=max(A[i],dp[i-1]+A[i]);
        }
        //寻找以A[i]结尾的最大序列和
        int k=0;
        for (int i=0;i<n;i++)
        { 
            if(dp[i]>dp[k])
                k=i;
        }
        for(int i=0;i<n;i++)
            printf("%d ",dp[i]);
        printf("\n");
        printf("%d %d\n",k,dp[k]);
        return 0;
    }
    /* 6 -2 11 -4 13 -5 -2 */

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200226231333327.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划算法的常用状态转移方程

我们一起走过了动态规划的世界，探索了爬楼梯问题、背包问题、最长递增子序列、最大子数组和以及最长公共子序列这五个经典问题。我们学习了如何定义状态，如何建立状态转移方程，如何...

分手后的思念是犯贱/ 2024年05月01日 05:50/ 0 赞/ 101 阅读

相关动态规划１：状态转移方程-求最大子序列和

时间复杂度Ｏ(n) 序列：-2 11 -4 13 -5 -2 //最大连续子序列和 //使用到状态转移方程 include <cstdio>

柔情只为你懂/ 2023年07月08日 15:29/ 0 赞/ 65 阅读

相关动态规划---最大公共子序列（连续）

比如：“abcdkkk” 和 “baabcdadabc”，可以找到的最长的公共子序列（连续）是"abcd",所以最大公共子序列长度（连续）为 4 代码： inc

矫情吗；*/ 2023年06月25日 02:23/ 0 赞/ 47 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

快来打我*/ 2022年09月23日 10:51/ 0 赞/ 238 阅读

相关【动态规划】求最长公共子序列

最长公共子串和最长公共子序列的区别： > 最长公共子串和最长公共子序列的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列

蔚落/ 2022年08月09日 00:59/ 0 赞/ 282 阅读

相关动态规划法-------最大连续子序列和

记得有次去索尼还有一个啥公司忘了名字，都问到了这个问题，找了下答案，特此记录一下：问题描述：数组 INT A\[\] = \{-4 , 3 ,56 , -15

红太狼/ 2022年08月05日 01:20/ 0 赞/ 209 阅读

相关动态规划（最大公共子序列）

> 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也

客官°小女子只卖身不卖艺/ 2022年06月05日 08:56/ 0 赞/ 217 阅读

相关最大连续子序列和-动态规划

题目描述：给定K个整数的序列\{ N1, N2, …, NK \}，其任意连续子序列可表示为\{ Ni, Ni+1, …, Nj \}，其中 1 <= i <= j <

川长思鸟来/ 2022年04月11日 06:13/ 0 赞/ 308 阅读

相关【谈谈】动态规划——求最长公共子序列

首先，我们要搞清楚所谓最长公共子序列的概念。不然很容易把它和最长公共子串混淆，两者区别是：子序列只需要字符保持相对顺序，并不要求像公共字串那样组成字符还需连续。问题：

素颜马尾好姑娘i/ 2022年01月31日 07:13/ 0 赞/ 278 阅读

相关求最长公共子序列（动态规划）

求最长公共子序列（动态规划）首先弄清楚，最长公共子串与最长公共子序列的区别：子串要求在原字符串中是连续的，而子序列则只需保持相对顺序一致，并不要求连续。比如说：A=\{

た入场券/ 2022年01月26日 03:11/ 0 赞/ 308 阅读