数组中子序列的最大乘积

问题描述：给定一个实数序列x1,x2,x3...xn，寻找一个连续的子序列Xi,Xi+1....Xj，使得其乘积在所有子序列乘积中最大。（为了简单考虑，不考虑数组含0的情况）
分析与解答：
归纳假设：已知如何找到规模小于n的序列的最大子序列。
这里直接考虑n>1的情况。由归纳，已知如何求出S'＝｛x1,x2...xn-1｝中的最大子序列，且子序列为Xi,Xi+1....Xj，其中1<=i<=j<=n-1。
若j=n-1，那么可以扩展到xn的情况，
如果xn大于0，那么最大值即为xn*S'，
如果xn<0，那么，我们还需要知道以n－1作为后缀的最小负乘积的子序列，设为S''，那么，只要比较S'和S''*xn的大小即可。

若j如果xn大于0，那么，我们还需要知道以n-1作为后缀的最大正数的乘积的子序列，设为S''，比较S'和S''*xn的大小即可。
如果xn<0，那么，我们还需要知道以n－1作为后缀的最小负乘积的子序列，设为 S''，那么，比较S'和S''*xn的大小即可。

所以，这里作更强的归纳假设：已知如何找到规模小于n的序列的最大子序列、作为后缀的最大子序列以及作为后缀的最小负数子序列。

这样，我们就将问题的规模从n降到了n-1，算法实现如下：

#include <stdio.h>

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x>y?y:x)

int max(int *a, int n)
{
    int i;
    int g_max=0;//全局最大
    int suffix_max=1;//作为后缀的最大子序列
    int suffix_min=1;//作为后缀的最小负数子序列
    int temp;
    for(i=0; i<n; i++)
    {
        if(a[i]>0)
        {
            g_max = MAX(suffix_max*a[i], g_max);
            suffix_max = MAX(suffix_max*a[i], a[i]);
            suffix_min = MIN(suffix_min*a[i], 1);
        }
        else if(a[i]<0)
        {
            temp = suffix_max;
            g_max = MAX(g_max, suffix_min*a[i]);
            suffix_max = MAX(suffix_min*a[i], 1);
            suffix_min = MIN(temp*a[i], 1);
        }
    }
    return g_max;
}
int main()
{
    int a[] = {2,3,1,-4,5,-2};
    printf("%d\n", max(a, 6));
    return 1;
}