利用C语言来求最大连续子序列乘积的方法
题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8。也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的。
提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续。也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别:
子串(Substring)是串的一个连续的部分,子序列(Subsequence)则是从不改变序列的顺序,而从序列中去掉任意的元素而获得的新序列;
更简略地说,前者(子串)的字符的位置必须连续,后者(子序列LCS)则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”,而它们的最长公共子序列LCS是“ adf ”,LCS可以使用动态规划法解决。
解答:
解法一、穷举,所有的计算组合:
或许,读者初看此题,自然会想到最大乘积子序列问题类似于最大子数组和问题:http://blog.csdn.net/v_JULY_v/article/details/6444021,可能立马会想到用最简单粗暴的方式:两个for循环直接轮询。
解法二、虽说类似于最大子数组和问题,但实际上具体处理起来诸多不同。为什么呢,因为乘积子序列中有正有负也还可能有0。我们可以把问题简化成这样:数组中找一个子序列,使得它的乘积最大;同时找一个子序列,使得它的乘积最小(负数的情况)。因为虽然我们只要一个最大积,但由于负数的存在,我们同时找这两个乘积做起来反而方便。也就是说,不但记录最大乘积,也要记录最小乘积。So,我们让maxCurrent表示当前最大乘积的candidate,minCurrent反之,表示当前最小乘积的candidate,而maxProduct则记录到目前为止所有最大乘积candidates的最大值。(以上用candidate这个词是因为只是可能成为新一轮的最大/最小乘积)由于空集的乘积定义为1,在搜索数组前,maxCurrent,minCurrent,maxProduct都赋为1。
假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates,新读入数组的元素x(i)后,新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者,如果x(i)<0导致maxCurrent<minCurrent,需要交换这两个candidates的值。当任何时候maxCurrent<1,由于1(空集)是比maxCurrent更好的candidate,所以更新maxCurrent为1,类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大,更新maxProduct。
解法三、本题除了上述类似最大子数组和的解法,也可以直接用动态规划求解(其实,上述的解法一本质上也是动态规划,只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的DP方程,而解法一是直接求解)。具体解法如下:
假设数组为a[],直接利用动归来求解,考虑到可能存在负数的情况,我们用Max来表示以a结尾的最大连续子串的乘积值,用Min表示以a结尾的最小的子串的乘积值,那么状态转移方程为:
Max=max{a, Max[i-1]*a, Min[i-1]*a};
Min=min{a, Max[i-1]*a, Min[i-1]*a};
初始状态为Max[1]=Min[1]=a[1]。
下面来看一道具体的ACM题目
题目
题目描述:
给定一个浮点数序列(可能有正数、0和负数),求出一个最大的连续子序列乘积。
输入:
输入可能包含多个测试样例。
每个测试样例的第一行仅包含正整数 n(n<=100000),表示浮点数序列的个数。
第二行输入n个浮点数用空格分隔。
输入数据保证所有数字乘积在双精度浮点数表示的范围内。
输出:
对应每个测试案例,输出序列中最大的连续子序列乘积,若乘积为浮点数请保留2位小数,如果最大乘积为负数,输出-1。
样例输入:
7 -2.5 4 0 3 0.5 8 -1 5 -3.2 5 -1.6 1 2.5 5 -1.1 2.2 -1.1 3.3 -1.1
样例输出:
12 64 8.78
思路
最大连续子序列乘积和最大连续子序列和不同,这里先回忆一下最大连续子序列和的最优解结构:
最大连续子序列和
我们用sum[i]来表示以arr[i]结尾的最大连续子序列和,则状态转移方程为:
最大连续子序列乘积
考虑存在负数的情况(ps:负负会得正),因此我们用两个辅助数组,max[i]和min[i],max[i]来表示以arr[i]结尾的最大连续子序列乘积,min[i]来表示以arr[i]结尾的最小连续子序列乘积,因此状态转移方程为:
and
有了状态转移方程,dp代码就很容易实现了,看到这里还不理解的同学,我建议你多花点时间用在算法学习上吧!
AC代码
#include <stdio.h> #include <stdlib.h> double maxNumInThree(double a, double b, double c) { double max; max = (a > b) ? a : b; max = (max > c) ? max : c; return max; } double minNumInThree(double a, double b, double c) { double min; min = (a < b) ? a : b; min = (min < c) ? min : c; return min; } int main(void) { int i, n; double *arr, *max, *min, res; while (scanf("%d", &n) != EOF) { arr = (double *)malloc(sizeof(double) * n); max = (double *)malloc(sizeof(double) * n); min = (double *)malloc(sizeof(double) * n); for (i = 0; i < n; i ++) scanf("%lf", arr + i); // 动态规划求最大连续子序列乘积 max[0] = min[0] = res = arr[0]; for (i = 1; i < n; i ++) { max[i] = maxNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]); min[i] = minNumInThree(arr[i], max[i - 1] * arr[i], min[i - 1] * arr[i]); if (max[i] > res) res = max[i]; } if (res >= 0) { // 判断是否为浮点数 if ((res - (int)res) == 0) printf("%d\n", (int)res); else printf("%.2lf\n", res); } else { printf("-1\n"); } free(arr); } return 0; }
/**************************************************************
Problem: 1501
User: wangzhengyi
Language: C
Result: Accepted
Time:110 ms
Memory:4964 kb
****************************************************************/
相关文章
- 这篇文章主要介绍了c++中system("pause")的作用和含义,非常不错,具有参考借鉴价值,需要的朋友参考下吧...2020-04-25
基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【八】框架功能总体界面介绍 的相关资料,需要的朋友可以参考下...2016-05-14- 这篇文章主要介绍了C# 16 进制字符串转 int的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
InterlliJ IDEA2020新建java web项目找不到Static Web的解决
这篇文章主要介绍了InterlliJ IDEA2020新建java web项目找不到Static Web的解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-09-02- 这篇文章主要介绍了C#类中static变量用法,实例分析了static变量使用技巧与相关注意事项,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了基于Ionic3实现选项卡切换并重新加载echarts,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-09-24
- 这篇文章主要给大家介绍C# winform快捷键设置技巧,涉及到C winform快捷键相关知识,对C winform知识感兴趣的朋友可以参考下本篇文章...2020-06-25
- 这篇文章主要介绍了C#判断一个字符串是否是数字或者含有某个数字的方法,本文给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 最近项目不多忙,于是抽点时间巩固下切换窗口问题,感兴趣的朋友跟着小编一起学习吧...2020-06-25
pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率
今天小编就为大家分享一篇pytorch绘制并显示loss曲线和acc曲线,LeNet5识别图像准确率,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-05-02基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化
这篇文章主要介绍了基于BootStrap Metronic开发框架经验小结【六】对话框及提示框的处理和优化的相关知识,主要对比说明在Bootstrap开发中用到的这些技术要点,对此文感兴趣的朋友一起学习吧...2016-05-14- 这篇文章主要为大家详细介绍了PC蓝牙通信C#代码实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-06-25
- 这篇文章主要介绍了C#实现带进度条的ListView 的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了SpringMVC文件上传原理及实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-07-15
基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)
这篇文章主要介绍了基于BootStrap的Metronic框架实现页面链接收藏夹功能按钮移动收藏记录(使用Sortable进行拖动排序)的相关资料,非常不错,需要的朋友可以参考下...2016-09-01- 这篇文章主要介绍了C#向线程中传递多个参数的解决方法(两种)的相关资料,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?
这篇文章主要介绍了C# MVC模式中应该怎样区分应用程序逻辑(Controller层)和业务逻辑(Model层)?,这也小编做.NET项目时经常思考和让人混乱的一个问题,这篇文章写的挺好,一下清晰了许多,需要的朋友可以参考下...2020-06-25基于Bootstrap的Metronic框架实现页面链接收藏夹功能
本文给大家介绍基于Metronic的Bootstrap开发框架实现页面链接收藏夹功能,非常不错,具有参考借鉴价值,感兴趣的朋友一起学习吧...2016-09-01ShardingSphere jdbc集成多数据源的实现步骤
本文主要介绍了ShardingSphere jdbc集成多数据源的实现步骤,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-10-21- 这篇文章介绍的是利用C#设置自定义文件图标,然后实现双击启动的功能,文章给出了示例代码,介绍的很详细,有需要的可以参考借鉴。...2020-06-25