给一个数字集合{ S1，S2，…，Sn }，请从这个数字集合里找出一段连续数字，使他们的乘积是最大的。 样例输入： 3 2 4 -3 5 2 5 -1 2 -1 3 -9 -7 -8 2 1 -1 1 -9 样例输出 Case #1: The maximum product is 8. Case #2: The maximum product is 20. Case #3: The maximum product is 63. Case #4: The maximum product is 1. Case #5: The maximum product is 0.
/* 紫书的例题 连续的子序列有两个要素，即起点和终点 因此只需枚举起点和终点即可，由于至多18个元素且绝对值不超过10，最大乘积不超过10的18次方，可以使用long long型存储。 以Case 1为例子，2 x 4 = 8为这个集合的最大乘积； 而Case 2则为2 x 5 x（–1）x 2 x（–1）=20。如果你找到的最大乘积小于等于0，则最后答案应输出0 */ #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int i,j,n,flag=0; long long s=1,maxx; int a[20]; while(~scanf("%d",&n)) { flag++; s=1; maxx=0; for(i=0;i<=n-1;i++) scanf("%d",&a[i]); for(i=0;i<=n-1;i++) { s=1; s*=a[i];//乘第一个数 if(maxx<s) maxx=s;//判断一下最大的乘积 for(j=i+1;j<=n-1;j++)//从 i 后一个开始相乘 { s*=a[j]; if(maxx<s) maxx=s; } } if(maxx<0) printf("0\n"); else printf("Case #%d:The maximum product is %lld.\n",flag,maxx); } } /* 该方法用了三个 for循环 再已知 子序列长度的情况下，去固定起点和终点 相当于当 长度是 1 的时候，去遍历 0，1，2，3，4 长度是2 的时候，去遍历 0~1，1~2，2~3，3~4 长度 3 的时候，遍历 0~2，1~3，2~4 长度是4的时候，去遍历 0~3，1~4 长度是 5的时候，去遍历 0~5 */ #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int i,j,k,n,flag=0; long long s=1,maxx; int a[20]; while(~scanf("%d",&n)) { flag++; s=1; maxx=0; for(i=0;i<=n-1;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++)//i:子序列的长度 是 1~n { for(j=0;j+i<=n;j++) // j:代表的是起点 //当长度 是 i的时候，起点应该满足 j+i<=n //例如 长度是1 的时候，起点应该是 0~5（此时 j是 0~4） // 长度是2的时候，起点应该是 0~4（此时 j是 0~3） { s=1; for(k=j;k<j+i;k++){//j:终点，终点应该小于起点+子序列的长度 s*=a[k]; maxx=max(maxx,s); } } } if(maxx<0) printf("0\n"); else printf("Case #%d:The maximum product is %lld.\n",flag,maxx); } } /* 暴力求解 遍历各个子序列（三个 for 循环） */ #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main() { int i,j,k,n,flag=0; long long s=1,maxx; int a[20]; while(~scanf("%d",&n)) { flag++; s=1; maxx=0; for(i=0;i<=n-1;i++) scanf("%d",&a[i]); for(i=0;i<=n-1;i++) { for(j=i;j<=n-1;j++){//起点 s=1; for(k=i;k<=j;k++){//终点 s*=a[k]; maxx=max(maxx,s);//利用 max 函数进行大小比较 } } } if(maxx<0) printf("0\n"); else printf("Case #%d:The maximum product is %lld.\n",flag,maxx); } }