当前位置: 代码迷 >> J2SE >> 求S[N]数组中任意N-1个元素的最大乘积,该如何解决
  详细解决方案

求S[N]数组中任意N-1个元素的最大乘积,该如何解决

热度:499   发布时间:2016-04-24 02:29:45.0
求S[N]数组中任意N-1个元素的最大乘积
有一个数组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)    }}
  相关解决方案