有一个数组S[N],求S[N]数组中 “任意“ N-1个元素的乘积,只能用乘法,不能用除法,要求时间复杂度为O(N)
------解决方案--------------------
- Java code
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) }}