OJ Board

Code: Select all

  code removed after accepted

Code: Select all

maxp[]

Code: Select all

if(c<maxp[i])
	c=maxp[i];

Code: Select all

3
0 -2 3
2
0 -2

Code: Select all

Case #1: The maximum product is 3.

Case #2: The maximum product is 0.

Code: Select all

5
1 2 -1 3 5
18
1 2 3 4 5 -1 2 2 3 4 5 7 4 2 1 0 -3

Code: Select all

Case #1: The maximum product is 15.

Case #2: The maximum product is 13440.

Code: Select all

Thanks Robert.

Code: Select all

2
-1 -1

Code: Select all

#include<iostream>
using namespace std;

long long subseq(int* seq,int number,int nz,int zero);

int main()
{
	int n,*seq,nz,*pos,count=0,zero,x;
	long long max,tmp,prod;
	while(cin>>n){
		x=n;
		++count;
		seq=new int[n];
		zero=max=nz=0;
		prod=1;
		for(int i=0; i<n; i++)
			seq[i]=-20;
		int j=-1;
		for(int i=0; i<n; i++){
			cin>>tmp;
			if(tmp==0){ 
				if(seq[j]==0) continue;
				zero++;
				nz++;
				seq[++j]=0; 
				prod=1; 
			}
			if(tmp<0){ 
				seq[++j]=tmp; 
				nz++; 
				prod=1; 
			}
			if(tmp>0){ 
				if(i==0 || prod==1) ++j;
				prod*=tmp; 
				seq[j]=prod; 
			}
		}
		for(int i=0; i<n; i++)
			if(seq[i]==-20){ x=i; break; }
		if(nz<=1 || (nz==2 && zero!=0) || !zero){
			max=subseq(seq,x,nz,zero);
			cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
			continue;
		}
		int a,b;
		max=nz=a=0;
		for(int i=0; i<x; i++){
			if(seq[i]==0 && a<i){
				tmp=subseq(&seq[a],i-a,nz,0);
				if(tmp>max) max=tmp;
				a=i+1;
				nz=0;
			}else if(seq[i]<0)
				nz++;
		}
		if(a!=x){
			tmp=subseq(&seq[a],x-a,nz,0);
			if(tmp>max) max=tmp;
		}
		cout<<"Case #"<<count<<": The maximum product is "<<max<<"."<<endl<<endl;
	}
	return 0;
}

long long subseq(int* seq,int n,int nz,int zero)
{
	int *pos;
	long long max=0,prod=1;
	if(nz<=1 || (nz==2 && zero!=0)){
		for(int i=0; i<n; i++)
			if(seq[i]>max) max=seq[i];
		return max;
	}
	pos=new int[nz];
	for(int i=0; i<nz; i++)
		pos[i]=-1;
	int j=0;
	for(int i=0; i<n; i++)
		if(seq[i]<=0) pos[j++]=i;
	prod=1;
	if(!(nz%2)){
		for(int i=0; i<n; i++)
			prod*=seq[i];
		max=prod;
		return max;
	}else{
		max=0;
		prod=1;
		for(int i=0; i<pos[nz-1]; i++)
			prod*=seq[i];
		max=prod;
		prod=1;
		for(int i=pos[0]+1; i<n; i++)
			prod*=seq[i];
		if(prod>max) max=prod;
		return max;
	}
}

Code: Select all

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = null;
		StringTokenizer st = null;
		int c = 1;
		
		boolean first = true;
		
		while((line = br.readLine())!=null) {
			
			//if (!first) 					// no newline after the last output
			//	System.out.println("\n");
			//first = false;
				
			int n = Integer.parseInt(line);
			int[] S = new int[n];
			st = new StringTokenizer(br.readLine());
			br.readLine();
			
			for (int i = 0; i<n; i++)
				S[i] = Integer.parseInt(st.nextToken());
			
			long product = 1;
			long max = 0;
			
			for (int i = 0; i<n; i++) {
				for (int j = i; j<n; j++) {
					for (int k = i; k<=j; k++)
						product*=S[k];
					if (product>max)
						max = product;
					product = 1;
				}
			}
			System.out.print("Case #"+c+++": The maximum product is "+max+".");
		}
		br.close();
	}

Code: Select all

Case #1: The maximum product is 8.Case #2: The maximum product is 20.