 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
C语言中求最大值的方法研究与实现
下载积分：280
内容提示：C语言中求最大值的方法研究与实现
文档格式：PDF|
浏览次数：88|
上传日期： 02:23:39|
文档星级：
该用户还上传了这些文档
C语言中求最大值的方法研究与实现
官方公共微信利用C语言来求最大连续子序列乘积的方法
作者：zinss26914
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了利用C语言来求最大连续子序列乘积的方法,基本的思路以外文中还附有相关ACM题目,需要的朋友可以参考下
题目描述：给一个浮点数序列，取最大乘积连续子串的值，例如 -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。&
&&& 样例输入：&&
-2.5 4 0 3 0.5 8 -1
-3.2 5 -1.6 1 2.5
-1.1 2.2 -1.1 3.3 -1.1
&&& 样例输出：&&
最大连续子序列乘积和最大连续子序列和不同，这里先回忆一下最大连续子序列和的最优解结构：
最大连续子序列和
我们用sum[i]来表示以arr[i]结尾的最大连续子序列和，则状态转移方程为：
最大连续子序列乘积
考虑存在负数的情况（ps：负负会得正），因此我们用两个辅助数组，max[i]和min[i],max[i]来表示以arr[i]结尾的最大连续子序列乘积，min[i]来表示以arr[i]结尾的最小连续子序列乘积，因此状态转移方程为：
有了状态转移方程，dp代码就很容易实现了，看到这里还不理解的同学，我建议你多花点时间用在算法学习上吧！
#include &stdio.h&
#include &stdlib.h&
double maxNumInThree(double a, double b, double c)
max = (a & b) ? a :
max = (max & c) ? max :
double minNumInThree(double a, double b, double c)
min = (a & b) ? a :
min = (min & c) ? min :
int main(void)
double *arr, *max, *min,
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 & i ++)
scanf("%lf", arr + i);
// 动态规划求最大连续子序列乘积
max[0] = min[0] = res = arr[0];
for (i = 1; i & 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);
printf("%.2lf\n", res);
printf("-1\n");
free(arr);
&&& /**************************************************************
&&&&&&& Problem: 1501
&&&&&&& User: wangzhengyi
&&&&&&& Language: C
&&&&&&& Result: Accepted
&&&&&&& Time:110 ms
&&&&&&& Memory:4964 kb
&&& ****************************************************************/&
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
C语言求最大值和最小值函数是哪个.
回※忆の870
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
c标准库中没有这类函数,可以自己写#define MAX(a,b) (a>b)?a:b
为您推荐：
其他类似问题
扫描下载二维码1943人阅读
算法竞赛入门经典（28）
printf(&%d\n&,~(unsigned int)0/2);
当无符号0以二进制存储在内存中时，每一位都为0，以32位int为例，0（unsigned int）的二进制为：
按位取反（~）后变成：
此时的十进制为：
除以2（int类型中有一半表示负数，且比正数多一个），得到：
即为32位int型最大值
#include &stdio.h&
int main()
int i=0,j=1;
while (j&0)
j++;
i++;
printf(&%d\n&,i);
printf(&%d\n&,j);
整数值越界后符号改变
#include &stdio.h&
int main()
i=i&&(sizeof(int)*8-1);
printf(&%d\n&,i);
printf(&%d\n&,i);
计算机采用补码存储，先补码得到-1（即各位全为1），然后利用移位运算得到最小，进而得到最大。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：35919次
积分：1237
积分：1237
排名：千里之外
原创：90篇
(6)(1)(1)(5)(36)(19)(23)(1)