DP--HDU 1003(最大子串和)

2024-06-14 08:32
文章标签 dp 最大 hdu 子串 1003

本文主要是介绍DP--HDU 1003(最大子串和),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题描述:
         给定整数A1, A2,……AN (可能有负数),求I到j的最大值。
例如:
         -2, 11, -4, 13, -5, -2时答案为20
  对于这个问题的算法有很多,当然我要说的是使用“动态规划”算法实现的程序,对于这个算法,我可以说很多人都曾经想到,但是没有想全(因为我就是这样的)。还有一点对于这个问题的动态规划的解法是非常经典的,她的时间复杂度是O(n),也就是线性的。而对于穷举法它的时间复杂度可是O(n3), 这样看来可以巨大的改进了。
  考虑这样的一个问题,我们从最简单的左边开始看,就如上面的例子,-2对于结果有影响吗?回答是没有。那么让我们看下面这样一个例子:
         6, -7, ……
         此时,我们还需要考虑6 和 –7 吗,有些人说要的,因为可能对于6,后面没有比其更大的了,是啊。问题是这样的。那么对于后面的结果分析其有影响吗?这个时候我们可以说没有影响的!
         到现在,上面是不是大家多曾经想到了呢?呵呵,我曾经就想到了,那我们为什么不把这问题,推倒后面呢?动态规划法就是解决这样的一个问题,我们知道此时前面的两个数就是一种最优的子结构(尽管只有2个数,不过是完全可以推广的。)
         书中的算法就告诉我们是如何推广的,我写这样的一篇文章的具体目的也就是为了说明以上的问题,因为我和大家一样都曾经想到了前面的算法,却没有考虑下去。以此感慨!并遗憾!
         那么书中的算法是这样的:(看这个算法之前应该先知道这个问题的“分治法”的求解,这样更让你觉得,这个算法的完美之处。)


Int MaxSubsequenceSum(const int A[], int N)
{int ThisSum, MaxSum, j;ThisSum = MaxSum = 0;For(j=0; j < N; j++)
{ThisSum += A[j];If (ThisSum > MaxSum)MaxSum = ThisSum;Else if(ThisSum < 0)ThisSum = 0;
}
return MaxSum;
} 

对于这个算法的分析(逻辑):

  从左相右相加,若结果不断的增加,那么ThisSum将同MaxSum一起增加,如果遇到负数,那么也加到ThisSum上去,但是此时ThisSum < MaxSum,那么就不加。看ThisSum是不是会回升,若一直不回升,不断或是波浪型的下降,那么当它降到0时,说明前一段与后一段是可以抛弃的。正如有 7 , -8 一样,我们可以不要这两个数,但是我们知道MaxSum依然保存着前一段的最大值,(这就是这个算法中的厉害,我认为)。然后,ThisSum将从后面开始将这个子段进行分析,若有比当前MaxSum大的子段,然后替换(此时可以彻底抛弃前一段)。这样一趟扫描结果也就出来了。
后记:
         对于这个问题,一开始对于分治算法,我们可能很容易想对,而对与动态规划可能我们很难想到(至少我没有那么轻易就想到了)。尽管如此,还是比较庆幸想到了其最优子结构,问题解决到此,当然对于这个问题,我们还是可以用“分治”算法,其时间复杂度为:O(nlogn),也是比较优的,当然没有上面提到的优。   

摘自:http://hi.baidu.com/longchengjiang/blog/item/7a5f2ad894a6d33733fa1c94%2Ehtml

补充:如果输入的所有整数为负,最大值为0.,原因是当子序列为空时,包含0个整数,也是子序列,它的和即为0,因为空子序列是连续的,所以总有一个连续子序列,它的和为0。(考虑空子序列的问题:空子序列也是子序列,它的和为0)


PS:MaxSum在这个算法中是一个中间变量,用来记录子问题的最值,而ThisSum是计算子问题的具体方法。

在网上搜到这篇,感觉讲得很通俗,易于理解。

下面附上此类问题的四种算法:


#include <iostream.h>
#include <stdio.h>
int MaxSubSum1( const int A[], int N);
int MaxSubSum2( const int A[], int N);
int MaxSubSum3( const int A[], int N);
int MaxSubSum4( const int A[], int N);const int M = 10;int main()
{int B[M];cout<< "请输入 " << M << " 个整数:  "<< endl;for ( int i=0; i < M; i++ ){cin>> B[i];}cout<< " 您输入的 " << M << " 个数为:  "<< endl;for ( i = 0; i < M; i++ ){cout<< B[i] <<", ";}cout<< " --------------------------------------- " << endl;cout<< "四个函数的运算结果分别为:" << endl;cout<< "-------------------------" << endl;cout<< MaxSubSum1( B, M ) << endl;cout<< MaxSubSum2( B, M ) << endl;cout<< MaxSubSum3( B, M ) << endl;cout<< MaxSubSum4( B, M ) << endl;return 0;
}int MaxSubSum1( const int A[], int N)  /*  第一种方法: 穷举 */
{int ThisSum, MaxSum;MaxSum = 0;for (int i=0; i < N; i++ ){for ( int j=i; j < N; j++ ){ThisSum = 0;for ( int k=i; k <= j; k++ ){ThisSum += A[k];}if ( ThisSum > MaxSum ){MaxSum = ThisSum;}}}return (MaxSum); 
}int MaxSubSum2( const int A[], int N)  /*  第二种方法: 分治 */
{int ThisSum, MaxSum;MaxSum = 0;for (int i=0; i < N; i++ ){ThisSum = 0;for ( int j=i; j < N; j++ ){ThisSum += A[j];if ( ThisSum > MaxSum ){MaxSum = ThisSum;}}}return (MaxSum); 
}/*  -----------------------------------------------------------------第三种方法: 二分法 */
static int BiMaxSubSum( const int A[], int Left, int Right );int MaxSubSum3 ( const int A[], int N ) 
{ return BiMaxSubSum ( A, 0, N - 1 ); 
}static int BiMaxSubSum( const int A[], int Left, int Right )
{int MaxSum, MaxLeftSum, MaxRightSum;int LeftBorderSum, RightBorderSum;int MaxLeftBorderSum, MaxRightBorderSum;int Center;if ( Left == Right ){if ( A[Left] > 0 ){return A[Left];}else{return 0;}} Center = ( Left + Right ) / 2;MaxLeftSum = BiMaxSubSum( A, Left, Center );MaxRightSum = BiMaxSubSum( A, Center + 1, Right );MaxLeftBorderSum = 0;LeftBorderSum = 0;for ( int i = Center; i >= Left; i-- ){LeftBorderSum += A[i];if ( LeftBorderSum > MaxLeftBorderSum ){MaxLeftBorderSum = LeftBorderSum;}}MaxRightBorderSum = 0;RightBorderSum = 0;for ( i = Center + 1; i <= Right; i++ ){RightBorderSum += A[i];if ( RightBorderSum > MaxRightBorderSum ){MaxRightBorderSum = RightBorderSum;}}MaxSum = ( (MaxRightSum > MaxLeftSum ) ? MaxRightSum : MaxLeftSum );int tmp = MaxRightBorderSum + MaxLeftBorderSum;return ( ( MaxSum > tmp ) ? MaxSum : tmp );
}int MaxSubSum4( const int A[], int N)  /*  第四种方法:  */
{int ThisSum, MaxSum;ThisSum = MaxSum = 0;for (int i=0; i < N; i++ ){ThisSum += A[i];if ( ThisSum > MaxSum ){MaxSum = ThisSum;}else if ( ThisSum < 0 ){ThisSum = 0;}}return (MaxSum); 
}



但是由于题目还要求 左右节点,,故法4修改如下

#include<iostream>
using namespace std;
int main()
{int T,n;int aq[100000];while(cin>>T){for(int k=1;k<=T;k++){cin>>n;for(int i=1;i<=n;i++)cin>>aq[i];int now=aq[1],sum=aq[1],left=1,right=1,oa=1;		for(int j=2;j<=n;j++){if(now<0){now=aq[j];oa=j;}else now+=aq[j];if(now>=sum){left=oa;right=j;sum=now;}}if(k!=1)cout<<endl;cout<<"Case "<<k<<":"<<endl<<sum<<" "<<left<<" "<<right<<endl;  }}return 0;
}


这篇关于DP--HDU 1003(最大子串和)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和