#include <stdlib.h>

int maxsubsum(int*,int,int,int*,int*);

int maxProduct(int* nums, int numsSize) {

int *s,*p; int result=0; int i; s=(int *) malloc(sizeof(int)*numsSize); if(s==NULL) exit(-1); for(i=0;i<numsSize;i++) s[i]=0; p=(int *) malloc(sizeof(int)*numsSize); if(p==NULL) exit(-1); for(i=0;i<numsSize;i++) p[i]=0; result = maxsubsum(nums,0,numsSize-1,s,p); free(s); free(p); return result;

}

int maxsubsum(int * a,int s ,int n ,intsum_max,intsum_min)
{

int i; int tmpa,tmpb; if(0==n) { sum_max[0]=a[0]; sum_min[0]=a[0]; return a[0]; } i=maxsubsum(a,0,n-1,sum_max,sum_min); tmpa=sum_max[n-1]*a[n]; tmpb=sum_min[n-1]*a[n]; if(tmpa>tmpb && tmpa>a[n]) sum_max[n]=tmpa; else if(tmpb>a[n]) sum_max[n]=tmpb; else sum_max[n]=a[n]; if(tmpa<tmpb && tmpa<a[n]) sum_min[n]=tmpa; else if(tmpb<a[n]) sum_min[n]=tmpb; else sum_min[n]=a[n]; if(i>sum_max[n]) return i; else return sum_max[n];

}