最大子序列乘积

给出最大子序列乘积（空子序列的最大子序列的积设为0），请给出适当的数学分析，程序也请给出适当注释，正确便给分

25 个解决方案

#1

#include <stdio.h>

int max(int i,int j,int k) //取最大数
{
if (j>i)  i=j;
if (k>i)  i=k;
return i;
}

int min(int i,int j,int k) //取最小数
{
if (j<i)  i=j;
if (k<i)  i=k;
return i;
}

void fun(int a[], int dp1[],int dp2[],int n)
{
int i,k;
dp1[0]=a[0];
dp2[0]=a[0];
for (i=1;i<n ;++i )
{
int tmp1= dp1[i-1]*a[i];
int tmp2= dp2[i-1]*a[i];
dp1[i]=max(tmp1,tmp2,a[i]);    //计算以当前数结尾的最大乘积
dp2[i]=min(tmp1,tmp2,a[i]);    //计算以当前数结尾的最小乘积
}
}

main()
{
int i,max_value=0;
int n,*ip,*dp1,*dp2;
scanf("%d",&n);
ip=(int*)malloc(n*sizeof(int));     //保存输入数据
dp1=(int*)malloc(n*sizeof(int)); //保存以当前数结尾的最大乘积
dp2=(int*)malloc(n*sizeof(int)); //保存以当前数结尾的最小乘积

for (i=0;i<n ;++i ) scanf("%d",ip+i);

fun(ip,dp1,dp2,n);

//最大乘积子序列要么是空子序列，要么是以某元素为结尾的子序列；
max_value=0; //取默认值为空子序列
for (i=0;i<n ;++i )
{
if (dp1[i]>max_value) max_value=dp1[i];
}

printf("%d\n",max_value);

return 0;
}

#2

这个序列是否有纯小数？是否有负数？
这将决定是否可采用一些对应的快速算法。

#3

我的程序只要
修改一下输入输出与数据类型就可以计算小数与负数了；

复杂度O(n);

#4

int替换为float后的程序：

#include <stdio.h>

float max(float i,float j,float k) //取最大数
{
if (j>i)  i=j;
if (k>i)  i=k;
return i;
}

float min(float i,float j,float k) //取最小数
{
if (j<i)  i=j;
if (k<i)  i=k;
return i;
}

void fun(float a[], float dp1[],float dp2[],float n)
{
int i,k;
dp1[0]=a[0];
dp2[0]=a[0];
for (i=1;i<n ;++i )
{
float tmp1= dp1[i-1]*a[i];
float tmp2= dp2[i-1]*a[i];
dp1[i]=max(tmp1,tmp2,a[i]);    //计算以当前数结尾的最大乘积
dp2[i]=min(tmp1,tmp2,a[i]);    //计算以当前数结尾的最小乘积
}
}

main()
{
int i,n;
float max_value=0;
float *ip,*dp1,*dp2;
scanf("%d",&n);
ip=(float*)malloc(n*sizeof(float));     //保存输入数据
dp1=(float*)malloc(n*sizeof(float)); //保存以当前数结尾的最大乘积
dp2=(float*)malloc(n*sizeof(float)); //保存以当前数结尾的最小乘积

for (i=0;i<n ;++i ) scanf("%f",ip+i);

fun(ip,dp1,dp2,n);

//最大乘积子序列要么是空子序列，要么是以某元素为结尾的子序列；
max_value=0; //取默认值为空子序列
for (i=0;i<n ;++i )
{
if (dp1[i]>max_value) max_value=dp1[i];
}

printf("%f\n",max_value);

return 0;
}

#5

楼上的，当“a[0] == 0”时？。。。

#6

回 ls:

没发觉当a[0]==0，结果有什么问题：

给个我的测试数据：
D:\projects\cl>test
6 0 -2 0 -4 5 -0.7
14.000000

#7

不过我的程序，子序列是连续的；
如果lz的说的子序列可以不连续；结果就是错的了；

#8

如果子序列可以不连续，题目就没什么难度了；

将所有的大与1的正数以及所有小于-1的负数相乘(假设乘积为p),并记录小于-1的负数的个数(假设个数为i),以及最小的小于-1的负数(假设为j),以及最大元素假设为k 就可以了；

若i<=1，结果为max(0,k);
若i为偶数，结果为p;
若i为奇数，结果为p/j;

#9

还没明白么？
在你的 fun() 函数中，当首元素为零时，后面的乘积永远为零！！！能得到的永远是空集。

#10

8楼漏了一个情况：

所有的数都是负数；
最大的乘积是两个大于-1的负数的乘积；

#11

“在你的 fun() 函数中，当首元素为零时，后面的乘积永远为零！！！能得到的永远是空集。”

你有测试？

给个我的测试数据：
D:\projects\cl> test
6 0 -2 0 -4 5 -0.7
14.000000

总共6个数，第一个数是0；

#12

对于子序列可以不连续的情况，我上面的描述有点问题，给个完整点的：

计算所有的大与1的正数以及所有小于-1的负数相乘(假设乘积为p);
计算小于-1的负数的个数(假设个数为i);
计算最小的小于-1的负数(假设为j)；
计算最大元素(假设为k)；
计算大于-1的两最大的负数假设为(m,n)；

1)若i=1 and p>0 结果为p;
2)若i=1 and p<0 结果为p;

若i为偶数，结果为p;
若i为奇数，结果为p/j;

#13

晕，12楼的帖子我没提交的呀；

越来越乱了；

#14

我本文写了一个函数，不知道正确不？

/*
这个问题其实可以简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个
子序列，使得它的乘积最小（负数的情况）。虽然我们只要一个最大积，但由于负数的
存在，我们同时找这两个乘积做起来反而方便。

我们让maxCurrent表示当前最大乘积的candidate，minCurrent反之，表示当前最小乘积
的candidate。这里我用candidate这个词是因为只是可能成为新一轮的最大/最小乘积，
而maxProduct则记录到目前为止所有最大乘积candidates的最大值。

由于空集的乘积定义为1，在搜索数组前，maxCurrent,maxProduct,minCurrent都赋为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。

*/
template <typename Comparable>
Comparable maxprod( const vector<Comparable>&v)
...{
    int i;
    Comparable maxProduct = 1;
    Comparable minProduct = 1;
    Comparable maxCurrent = 1;
    Comparable minCurrent = 1;
    //Comparable t;

    for( i=0; i< v.size() ;i++)
    ...{
        maxCurrent *= v[i];
        minCurrent *= v[i];
        if(maxCurrent > maxProduct)
            maxProduct = maxCurrent;
        if(minCurrent > maxProduct)
            maxProduct = minCurrent;
        if(maxCurrent < minProduct)
            minProduct = maxCurrent;
        if(minCurrent < minProduct)
            minProduct = minCurrent;
        if(minCurrent > maxCurrent)
            swap(maxCurrent,minCurrent);
        if(maxCurrent<1)
            maxCurrent = 1;
        //if(minCurrent>1)
        //    minCurrent =1;
    }
    return maxProduct;

}

#15

to tailzhou:
对不起，确实没作测试。我没有去仔细读你的for循环中的语句，所以以为后面的永远为0。
这个问题的“子序列”显然不要求连续性（相信楼主也是这么认为），由于先入为主问题，所以误读了你的程序。

#16

to: lz
"空子序列的最大子序列的积设为0;"
"由于空集的乘积定义为1"

好象有矛盾；

看你的程序，子序列应该是可以不连续的；

当v[i]单个元素就是最大乘积的时候，你的程序有bug；

maxCurrent   *=   v[i];
minCurrent   *=   v[i];

之后，
maxProduct应该取 max（maxProduct,maxCurrent,minCurrent   ,v[i])
minProduct应该取 min（minProduct,maxCurrent,minCurrent   ,v[i])

#17

"if(maxCurrent <1)
                        maxCurrent   =   1;
"
原来你后面处理过了；

但这里有个问题：
假设
在计算maxCurrent   *=   v[i]之前的时候  maxCurrent>1
在计算maxCurrent   *=   v[i]之后的时候  maxCurrent<1


由于你做了maxCurrent   =   1;的修正，之后的乘积不再计算前面的元素；所以不可能计算出不连续的子序列的乘积；

lz要说清楚到底是连续还是不连续；

#18

确实，空子序列的最大子序列的积"设为0" 改为 "设为1" 可能更恰当些，好比 0!=1

#19

对于子序列可以不连续的情况，有比较多的特殊情况需要考虑：

一.计算所有的大于等于1的正数（假设有i个）以及所有小于等于-1的负数(假设有j个)的乘积(假设乘积为p);
二.计算大于-1的最小负数（假设为m1）以及小于-1的最大负数(假设为m2);
三.计算最小的两负数（假设为f1,f2）以及最大的数(f3);
  1. 若 i>0 或者 j>=2
    a) 若 p>0,则结果为p;
    b) 若 p<0 and m1存在 and m1*m2>1  则结果为 p*m1;
    c) 若 p<0 and (m1不存在  or m1*m2<1)  则结果为 p/m2;
  2. 若 j==1 and m1存在 and m1*n>1  则结果为 p*m1;
  3. 其他情况,结果为 max(0,f3,f1*f2);

#20

lz的程序改成这样测试看看；

maxProduct  =0;
minProduct  =0;
for(   i=0;   i <   v.size()   ;i++)
{
maxCurrent   = maxProduct   * v[i];
minCurrent   = minProduct   * v[i];

maxProduct=max(maxProduct,maxCurrent   , minCurrent   ,V[i])
minProduct=min(minProduct   ,maxCurrent   , minCurrent   ,V[i])
}

#21

是可能改成1更恰当，子序列是连续的，
to：tailzhou
我的程序不改好像也没有问题吧，我测试了一些数据，好像没有问题，要不你给我举个反例。先谢谢了

#22

改成1我觉得不合适；
比如： 0.1 0.2 0.3 0.4
的最大子序列乘积是0。4还是1更合理？？

如果是连续的，我开始贴的程序就可以用；

我们几次问你是连续还是不连续的了，你一直置之不理；
别人都认为你的要求是不连续的，如果是求不连续的，你的程序就是错误的；

#23

我当时没有上网，不好意思。

#24

mark先

#25

#1

#2