|
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Input: [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray. #include <iostream> using namespace std; //求最大值 int max_num(int* input, int i, int j){ int max = 1; for(int k = i;k<j;k++) max*=input[k]; return max; } //按負數(shù)劃分 int split_neg_one(int* input, int i, int j){ int num_neg = 0; for(int k = i;k<j;k++) { cout<<"k-th num:"<<input[k]<<endl; if(input[k]<0) num_neg += 1; } cout<<"num of num_neg:"<< num_neg<<endl; if(num_neg % 2 == 0) //如果有偶數(shù)個-1 { cout<<"even number"<<endl; return max_num(input,i,j); } else { //如果有奇數(shù)個-1 int max = 0x80000000; for(int k = i;k<j;k++){ if(input[k]<0){ int temp = max_num(input,i,k)> max_num(input,k+1,j)?max_num(input,i,k): max_num(input,k+1,j); cout<<"split one i, k, temp:"<<i<<" "<<k<<" "<<temp<<endl; max = max>temp?max:temp; } } return max; } } //按0劃分 int split_zero(int* input, int i , int j) { int start = i; int max = 0x80000000; bool flag_zero = false; cout<<"begin"<<endl; for(int k = i; k<j;k++) { if(input[k]==0) { max = max > 0? max:0; cout<<"zero position:"<<k<<endl; flag_zero=true; if(k != i) { int temp = split_neg_one(input,start,k); cout<<"split negtive one:"<<max<<endl; max = max > temp ? max:temp; cout<<"max temp compare:"<<max<<endl; start=k+1; } } if(k==j-1){ int temp = split_neg_one(input,start,j); cout<<"split last:"<<start<<" "<<j<<" temp:"<<temp<<endl; max = max > temp ? max:temp; } } if(!flag_zero){ max = split_neg_one(input,i,j); cout<<"point 1:"<<endl; } return max; } int process(int * input, int length){ if(input==NULL || length < 0) return 0x80000000; split_zero(input,0,length); } int main() { int input[]={2 , 3 ,2, 1, 0, 1, 4, -1, -2,-3,-4,-5}; int length = sizeof(input)/sizeof(int); cout <<"result:"<<process(input,length)<< endl; } |
|
|
