hdoj 1003 Max Sum---动态规划,最大子序列求和

2024-06-13 20:38

本文主要是介绍hdoj 1003 Max Sum---动态规划,最大子序列求和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

初来乍到,动态规划不会呀,刚开始用暴力法,超时了!超时代码如下:

思路:大致是选中一个数当做结尾,然后加和。例如在6 -1 5 8 -7选中5作为结尾大致有如下序列

6  -1   5

    -1   5

          5

就这样遍历所以的结尾,结果超时。代码如下:

#include<iostream>
#include<algorithm>
using namespace std;#define VALUE 101
#define INF 999999999int D[VALUE];
int n;
int t;
int sum;
int maxSum[VALUE][VALUE]={0};
int  x,y;
int T=1;
int main() {int i, j, k;cin >> n;while (n--) {cin >> t;for (i = 1; i <= t; i++) {cin >> D[i];}for (i = 1; i <= t; i++) { //选那个结束for (j = 1; j <= i; ++j) {  //有多少行sum = 0;for (k = j; k <= i; k++) {  //每一个行有多少个相加sum = sum + D[k];}maxSum[j][i] = sum;}}int max = -INF;for (i = 1; i <= t; i++) {for (j = 1; j <= i; j++) {if (max < maxSum[j][i]) {max = maxSum[j][i];x = j;y = i;}}}cout << "Case " << T << ":" << endl;T++;cout << max << " " << x << " " << y << endl;if (n != 0) {cout << endl;}}
}

      在网上搜了代码。大多是只说是动态规划经典问题、求最大子序列和,终于算是有了眉目想通了。

对于整个序列a[n]来说,它的所有子序列有很多很多,但是可以将它们归类。
注意,是以**结尾的子序列,其中肯定是要包含**的了
 
以a[0]结尾的子序列只有a[0]
以a[1]结尾的子序列有    a[0]a[1]和a[1]
以a[2]结尾的子序列有    a[0]a[1]a[2]   /  a[1]a[2]  / a[2]
……
以a[i]结尾的子序列有a[0]a[1]……a[i-2]a[i-1]a[i]   / a[1]a[2]……a[i-2]a[i-1]a[i]  /  a[2]a[3]……a[i-2]a[i-1]a[I]  / …… /  a[i-1]a[i] / a[i]
 
所有以a[0] ~a[n]结尾的子序列分组构成了整个序列的所有子序列。
 
这样,我们只需求以a[0]~a[n]结尾的这些分组的子序列中的每一分组的最大子序列和。然后从n个分组最大子序列和中选出整个序列的最大子序列和。
 
观察可以发现,0,1,2,……,n结尾的分组中,
maxsum a[0] = a[0]
maxsum a[1] = max( a[0] + a[1] ,a[1])  = max( maxsum a[0] + a[1] ,a[1]) 
maxsum a[2] = max( max ( a[0] + a[1] + a[2],a[1] + a[2] ),a[2])  
= max(  max( a[0] + a[1] ,a[1]) + a[2] , a[2]) 
= max(  maxsum a[1] + a[2] , a[2])
……
依此类推,可以得出通用的式子。
maxsum a[i] = max( maxsum a[i-1] + a[i],a[i])
 

最大子段和:给定一个序列(元素可正可负),找出其子序列中元素和最大的值。

我们用dp(i)表示序列中以元素ans(i)结尾的序列的最大子段和,那么有:dp(i)=max(dp(i-1)+ans(i),ans(i));

首先来看一道比较基础的最大子段和问题--HDOJ 1003   Max Sum:

#define INF 999999999
int solve(int ans[],int n)  
{  dp[0]=0;  int nmax=-INF;  for(int i=1;i<=n;i++)  {  dp[i]=max(dp[i-1]+ans[i],ans[i]);  nmax=max(nmax,dp[i]);  }  return nmax;  
}  

题目大意:给定一个序列,让求出此序列的最大子段和,并输出该子序列在原序列中的位置。

这里我们用变量sum来代替dp()数组,如果sum+a(i)<a(i),就更新sum的值,并重新纪录head的值,如果sum+a(i)>=a(i),则只需更新sum的值;

代码如下:

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;#define  MAX 100005
int n;
int t;
int a[MAX]={0};
int main() {int i, j, k;cin >> t;int head, tail;int sum, max;int x;int T = 0;while (t--) {T++;cin >> n;for (i = 1; i <= n; i++) {cin >> a[i];}head = tail = x = 1;sum = max = a[1];for (i = 2; i <= n; i++) {if (sum + a[i] < a[i]) {   //重新定义开始的头x = i;sum = a[I];  //会导致sum大于max} else {sum = sum + a[i];}if (sum > max) {  //一般sum和max相等,sum大于max,说明加到一个正数。或者上一次循环中sum等于max,更新head和tail。max = sum;tail = i;head = x;}}cout << "Case " << T << ":" << endl << max << " " << head << " " << tail << endl;if (t) {cout << endl;}}
}

其他人代码:
    #include <iostream>  using namespace std;  int main()  {  int j,i,k,n,m,t;  int a[100002];  scanf("%d",&t);  for (j=1;j<=t;j++)  {  scanf("%d",&n);  for (i=0;i<n;i++)  {  scanf("%d",&a[i]);  }  int sum=0,maxsum=-1001,first =0, last = 0, temp = 1;  for (i=0;i<n;i++)  {  sum += a[i];  if (sum > maxsum)  {  maxsum = sum;first = temp;last = i+1;  }  if (sum < 0)  {  sum = 0;temp = i+2;  }  }  printf("Case %d:\n%d %d %d\n",j,maxsum,first,last);  if (j!=t)  {  printf("\n");  }  }  return 0;  } 
对于整个序列a[n]来说,它的所有子序列有很多很多,但是可以将它们归类。
注意,是以**结尾的子序列,其中肯定是要包含**的了
 
以a[0]结尾的子序列只有a[0]
以a[1]结尾的子序列有 a[0]a[1]和a[1]
以a[2]结尾的子序列有 a[0]a[1]a[2] / a[1]a[2] / a[2]
……
以a[i]结尾的子序列有a[0]a[1]……a[i-2]a[i-1]a[i]  / a[1]a[2]……a[i-2]a[i-1]a[i] /  a[2]a[3]……a[i-2]a[i-1]a[i] / …… /  a[i-1]a[i] / a[i]
 
所有以a[0] ~a[n]结尾的子序列分组构成了整个序列的所有子序列。
 
这样,我们只需求以a[0]~a[n]结尾的这些分组的子序列中的每一分组的最大子序列和。然后从n个分组最大子序列和中选出整个序列的最大子序列和。
 
观察可以发现,0,1,2,……,n结尾的分组中,
maxsum a[0] = a[0]
maxsum a[1] = max( a[0] + a[1] ,a[1])  =  max( maxsum a[0] + a[1] ,a[1]) 
maxsum a[2] = max( max ( a[0] + a[1] + a[2],a[1] + a[2] ),a[2])  
= max(  max( a[0] + a[1] ,a[1]) + a[2] , a[2]) 
= max(  maxsum a[1] + a[2] , a[2])
……
依此类推,可以得出通用的式子。
maxsum a[i] = max( maxsum a[i-1] + a[i],a[i])
 
 
用递归……当然,不递归也应该是可以解决的。
 
我们从maxsum  a[0]开始算起。
以后的每个就是  maxsum a[i-1] + a[i] 和 a[i] 中取大的那个
 
程序中判断 前一个的最大子序列和小于零时,将其置为0,然后再加a[i] ,这样不就是和a[i] 一样大的么;前一个的最大子序列和只要大于零,那么再加上a[i] 肯定比 a[i] 要大,这样,带有归零的这个 maxsum a[i-1] + a[i] 就是以表示当前位置结束的子序列的最大和了。
 
 
剩下的就是要判断起始和终点位置了。
 
在循环的过程中,每循环一次就算出一个以当前位置结束的最大子序列和。每次循环中最大的那个保存下来,不就是最终所有最大子序列和中的最大值了么。
 
其中temp保存的是前一个位置的最大子序列和的开始位置(题目中是从1开始的哦);当 sum > maxsum 时( 程序中的条件,与说明时的maxsum不太一样哦 )就记录最大值,并保持它的开始位置为temp,终止位置即为当前位置(i +1是因为题目中第一个为1,而不是0);
 
当最大子序列和小于0时,将 temp = i + 2; 其中 i + 1 表示当前位置(理由如上),i + 2就表示当前位置的下一个位置了。既此最大子序列和为负值,那么下一个的最大子序列和应该是它本身,而不再累加前边的。
 
程序中就两个if 语句,想要说明白还真不容易。
 
还有,有人会问,当整个序列全是负数时,还对吗?负数也是成立的,如果全是负数的时候,它就是每次都只取当前值作为最大值了,因为负的跟负的不就越加越小了吗。
 
因为题目中给出的范围是-1000 ~1000,所以 这里初始的maxsum 初始化为-1001 ,只有比所有可能的值都小时才行。maxsum初始化为0;那么当序列全是负数时,得出的最大值将是0……这就wrong了
 
 总之,只要上一个子序列最大和为正,那么无论当前值的正负,都会与当前的相加,这样以当前值结尾的子序列最大和就会增大。(一个正数 加一个 正数2 或者负数 那么都会比这个正数2 或负数原来要增大,同理,一个负数加任何一个数,都会使这个数减小,因此当前一子序列最大和小于零时,我们就归零它了,相当于是不加任何数,而保留当前位置值本身)
 

内存优化版:
    理解了以上思想后,观察上一个代码我们发现,那个a[10000]基本上就没用啊,保存了一些输入数据,可是那些数据只用了一次就没用了。输入数据的for循环和处理数据的for循环是一模一样的,而且处理数据也只是用到当前输入的数据。
于是,数组也可以省去了,直接将两个循环合并。输入一个数据,直接累加……省下不少空间哦。
复制代码
 1     #include <iostream>  
 2     using namespace std;  
 3     int main()  
 4     {  
 5         int j,i,k,n,m,t;  
 6         int a;  //不需要数组,只需要一个输入变量
 7         scanf("%d",&t);  
 8         for (j=1;j<=t;j++)  
 9         {  
10             scanf("%d",&n);  
11             int sum=0,maxsum=-1001,first =0, last = 0, temp = 1;  
12             for (i=0;i<n;i++)  
13             {  
14                 scanf("%d",&a); 
15                 sum += a;  
16                 if (sum > maxsum)  
17                 {  
18                     maxsum = sum;first = temp;last = i+1;  
19                 }  
20                 if (sum < 0)  
21                 {  
22                     sum = 0;temp = i+2;  
23                 }  
24             }  
25       //注意格式,我就因为将冒号写到了数的前边而wrong answer,郁闷半天才发现……
26             printf("Case %d:\n%d %d %d\n",j,maxsum,first,last);  
27             if (j!=t)  
28             {  
29                 printf("\n");  
30             }  
31         }  
32           
33         return 0;  
34     }  
复制代码

 

这篇关于hdoj 1003 Max Sum---动态规划,最大子序列求和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1058365

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态