服务器之家

服务器之家 > 正文

利用C语言来求最大连续子序列乘积的方法

时间:2021-03-06 14:12     来源/作者:zinss26914

题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -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。 
    样例输入:  

?
1
2
3
4
5
6
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]结尾的最大连续子序列和,则状态转移方程为:

利用C语言来求最大连续子序列乘积的方法

最大连续子序列乘积
考虑存在负数的情况(ps:负负会得正),因此我们用两个辅助数组,max[i]和min[i],max[i]来表示以arr[i]结尾的最大连续子序列乘积,min[i]来表示以arr[i]结尾的最小连续子序列乘积,因此状态转移方程为:

利用C语言来求最大连续子序列乘积的方法

and

利用C语言来求最大连续子序列乘积的方法

有了状态转移方程,dp代码就很容易实现了,看到这里还不理解的同学,我建议你多花点时间用在算法学习上吧!

AC代码

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#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
    ****************************************************************/ 

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部