求S[N]数组中任意N-1个元素的最大乘积

Question

  有一个数组S[N]，求S[N]数组中 “任意“ N-1个元素的乘积，只能用乘法，不能用除法，要求时间复杂度为O(N)

Answer 1

public class Test {
    http://wenku.baidu.com/view/6607b3360b4c2e3f5727631d.html
    public static void main(String[] args) {
int s[] = {5,-3,2,4,-1,3};
int length = s.length;
int[] front = new int[length];//前i个数的积
int[] back = new int[length];// 倒数i个数的积

front[0] = s[0];
back[0] = s[length-1];
for(int i=1; i<length; i++){
  front[i] = front[i-1]*s[i];
  back[i] = back[i-1]*s[length-i-1];
}

int result = back[length-2]>front[length-2]?back[length-2]:front[length-2];
for(int i=1;i<length-1;i++){
    int temp = front[i-1]*back[length-i-2];
    if(result< temp) result = temp;     
}
System.out.println(result);

//O(n) + O(n)  = O(n)
    }
}