應用C說話來求最年夜持續子序列乘積的辦法。本站提示廣大學習愛好者：（應用C說話來求最年夜持續子序列乘積的辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是應用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
****************************************************************/
