HDU1003 Max Sum 最大子序列和的问题【四种算法分析+实现】

2023-11-11 06:10

本文主要是介绍HDU1003 Max Sum 最大子序列和的问题【四种算法分析+实现】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

就拿杭电OJ上的第1003题开始吧,这题比原书要复杂一些。

Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
 
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
 
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
 
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
 
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6

题意很简单,那么就开始分析了,最容易想到的方法自然是枚举,只需要枚举出所有的可能情况。

具体实现如下:

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn];int main(){int t, n, maxLeft, maxRight, maxSum, id = 1;int thisSum;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;/*maxSubsequenceSum------O(N^3)*/for(int i = 0; i < n; ++i){for(int j = i; j < n; ++j){thisSum = 0;for(int k = i; k <= j; ++k){thisSum += arr[k];}if(thisSum > maxSum){maxSum = thisSum;maxLeft = i; maxRight = j;}}}printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

结果是意料之中的超时



接下来我们再换一个效率高点的算法。其实上一个算法中第三层for循环可以去掉,让第二层表示以arr[i]为起点的子序列,就这样一直向右加下去,如果和大于maxSum,那么就更新值。实现如下:

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn]; int main(){int t, n, maxLeft, maxRight, maxSum, id = 1;int thisSum;scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;/*maxSubsequenceSum------O(N^2)*/for(int i = 0; i < n; ++i){thisSum = 0;for(int j = i; j < n; ++j){thisSum += arr[j];if(thisSum > maxSum){maxSum = thisSum;maxLeft = i;maxRight = j;}				}}printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

依旧超时


只能再换效率更高算法,对于最大子序列和这个问题其实可以细分成多个子问题来求解,再将子问题的解合并,于是可以考虑下分治法,具体实现如下:

#include <stdio.h>
#define maxn 100000 + 2
int arr[maxn]; 
int t, n, maxLeft, maxRight, maxSum, id = 1;int max3(int a, int b, int c){if(a >= b && a >= c) return 1;if(b >= a && b >= c) return 2;if(c >= a && c >= b) return 3;
}int maxSubsequenceSum(int left, int right, int *l, int *r){int thisLeft, thisRight;int leftSum, rightSum, midSum, mid;int leftBorderSum, maxLeftBorderSum;int rightBorderSum, maxRightBorderSum;int ll, lr, rl, rr, ml, mr;if(left == right){*l = *r = left;return arr[left];}mid = (left + right) / 2;leftSum = maxSubsequenceSum(left, mid, &ll, &lr);rightSum = maxSubsequenceSum(mid + 1, right, &rl, &rr);leftBorderSum = 0; thisLeft = mid;maxLeftBorderSum = arr[mid];for(int i = mid; i >= left; --i){leftBorderSum += arr[i];if(leftBorderSum >= maxLeftBorderSum){maxLeftBorderSum = leftBorderSum;thisLeft = i;}}rightBorderSum = 0; thisRight = mid + 1;maxRightBorderSum = arr[mid + 1];for(int i = mid + 1; i <= right; ++i){rightBorderSum += arr[i];if(rightBorderSum > maxRightBorderSum){maxRightBorderSum = rightBorderSum;thisRight = i;}}midSum = maxLeftBorderSum + maxRightBorderSum;   int sign = max3(leftSum, midSum, rightSum);if(sign == 1){maxSum = leftSum;*l = ll;*r = lr;}else if(sign == 2){maxSum = midSum;*l = thisLeft;*r = thisRight;}else{maxSum = rightSum;*l = rl;*r = rr;}return maxSum;
}int main(){    scanf("%d", &t);while(t--){scanf("%d", &n);for(int i = 0; i < n; ++i)scanf("%d", &arr[i]);maxSum = arr[0];maxLeft = maxRight = 0;maxSubsequenceSum(0, n - 1, &maxLeft, &maxRight);printf("Case %d:\n%d %d %d\n", id++, maxSum, maxLeft + 1, maxRight + 1);if(t) printf("\n");}return 0;
}

终于AC了!


书上还介绍了一个狂拽酷炫叼炸天的O(n)算法,这里也尝试一下,再对比一下与分治法的时间消耗。改的过程真是相当得不顺利,WA了5次左右才改对,不过把数组开销都省了,真心够精简的。

#include <stdio.h>int main(){int t, n, maxLeft, maxRight, maxSum, temp;int thisLeft, thisSum;scanf("%d", &t);for(int id = 1; id <= t; ++id){scanf("%d", &n);scanf("%d", &maxSum);thisLeft = maxLeft = maxRight =  0;thisSum = maxSum;if(thisSum < 0){ thisSum = 0; thisLeft = 1; }for(int i = 1; i < n; ++i){scanf("%d", &temp);thisSum += temp;if(thisSum > maxSum){maxSum = thisSum;maxLeft = thisLeft;maxRight = i;}if(thisSum < 0){thisLeft = i + 1;thisSum = 0;}}printf("Case %d:\n%d %d %d\n", id, maxSum, maxLeft + 1, maxRight + 1);if(id != t) printf("\n");}return 0;
}

时间开销如下


呼呼,四种算法总算都实现了。实现过程虽然很受挫,但是很充实的说,结果也很让人愉快,A wonderful day~




这篇关于HDU1003 Max Sum 最大子序列和的问题【四种算法分析+实现】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

Mysql的主从同步/复制的原理分析

《Mysql的主从同步/复制的原理分析》:本文主要介绍Mysql的主从同步/复制的原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录为什么要主从同步?mysql主从同步架构有哪些?Mysql主从复制的原理/整体流程级联复制架构为什么好?Mysql主从复制注意

IDEA如何实现远程断点调试jar包

《IDEA如何实现远程断点调试jar包》:本文主要介绍IDEA如何实现远程断点调试jar包的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录问题步骤总结问题以jar包的形式运行Spring Boot项目时报错,但是在IDEA开发环境javascript下编译

Python实现自动化Word文档样式复制与内容生成

《Python实现自动化Word文档样式复制与内容生成》在办公自动化领域,高效处理Word文档的样式和内容复制是一个常见需求,本文将展示如何利用Python的python-docx库实现... 目录一、为什么需要自动化 Word 文档处理二、核心功能实现:样式与表格的深度复制1. 表格复制(含样式与内容)2

python获取cmd环境变量值的实现代码

《python获取cmd环境变量值的实现代码》:本文主要介绍在Python中获取命令行(cmd)环境变量的值,可以使用标准库中的os模块,需要的朋友可以参考下... 前言全局说明在执行py过程中,总要使用到系统环境变量一、说明1.1 环境:Windows 11 家庭版 24H2 26100.4061

如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

《如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socketreadtimedout的问题》:本文主要介绍解决Druid线程... 目录异常信息触发场景找到版本发布更新的说明从版本更新信息可以看到该默认逻辑已经去除总结异常信息触发场景复

Python中bisect_left 函数实现高效插入与有序列表管理

《Python中bisect_left函数实现高效插入与有序列表管理》Python的bisect_left函数通过二分查找高效定位有序列表插入位置,与bisect_right的区别在于处理重复元素时... 目录一、bisect_left 基本介绍1.1 函数定义1.2 核心功能二、bisect_left 与

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

pandas实现数据concat拼接的示例代码

《pandas实现数据concat拼接的示例代码》pandas.concat用于合并DataFrame或Series,本文主要介绍了pandas实现数据concat拼接的示例代码,具有一定的参考价值,... 目录语法示例:使用pandas.concat合并数据默认的concat:参数axis=0,join=

java -jar命令运行 jar包时运行外部依赖jar包的场景分析

《java-jar命令运行jar包时运行外部依赖jar包的场景分析》:本文主要介绍java-jar命令运行jar包时运行外部依赖jar包的场景分析,本文给大家介绍的非常详细,对大家的学习或工作... 目录Java -jar命令运行 jar包时如何运行外部依赖jar包场景:解决:方法一、启动参数添加: -Xb