数组中的元素相乘

Question

我正在尝试解决问题。我们将在O（n）中找到一个数组的maxProduct，因此它没有双重循环，因为它将是O（n2） 您将在我的代码中看到，除第一个元素和最后的元素。我怎样才能使用我的代码的逻辑来扩充我的数组的第一个和最后一个元素？

这里是我的代码：

public class Maxprod { 
public static void main(String [] args){ 
    Maxprod myclass = new Maxprod(); 
    myclass.maxProduct(); 
} 

public void maxProduct(){ 
    int [] myarr = {4, -5, -7, 5}; 
    int max = 0, p=0; 
    int q = 0; 

    for(int i=0; i <myarr.length-1; i++){ 
     p = myarr[i]*myarr[i+1]; // 4 * 5 is missing here 
     if (p > max){ 
      max = p; 
     } 
    } 
    System.out.println(max); 
} 

} 

Answer 1

你的代码的情况似乎比你想象的还要糟糕;从我看到你不仅错过（4 * 5），还错过（4 * -7）和（-5 * -5）。你确定你只想要连续的数字吗？你也错过了（-7 * 5），因为你的for循环条件是关闭的。

要回答你的最直接的问题，初始化p来（开始*结束）：

p = myarr[0] * myarr[myarr.length-1]; 
for(int i=0; i <myarr.length; i++){ 
    p = myarr[i]*myarr[i+1]; // 4 * 5 is missing here 
    if (p > max){ 
     max = p; 
    } 
} 
System.out.println(max); 

如果你真的想maxProduct，考虑到所有排列，在O（n）的，你需要跟踪两个最大的正数和两个最大的负数。考虑这样的事情：

public void maxProduct(){ 
    int [] myarr = {4, -5, -7, 5}; 
    int max = 0, maxn = 0, maxp = 0; 
    int n1 = 0, n2 = 0; 
    int p1 = 0, p2 = 0; 

    for(int i=0; i <myarr.length; i++){ 
     // Store greatest negative pair 
     if (myarr[i] < n1) { 
      n2 = n1; 
      n1 = myarr[i]; 
     } 

     // Store greatest positive pair 
     if (myarr[i] > p1) { 
      p2 = p1; 
      p1 = myarr[i]; 
     } 
    } 

    maxn = n1 * n2; 
    maxp = p1 * p2; 
    if (maxn > maxp) { 
     max = maxn; 
    } else { 
     max = maxp; 
    } 

    System.out.println(max); 
}