배열의 요소 곱하기

Question

문제점을 해결하려고합니다. 우리는 O (n)에서 배열의 maxProduct를 찾을 것이므로 O (n²)가 될 것이기 때문에 허용 된 루프에 대한 이중 값이 없습니다 모든 코드가 첫 번째 및 마지막 요소. 내 코드의 논리를 사용하여 배열의 첫 번째 요소와 마지막 요소를 어떻게 곱할 수 있습니까? 여기

내 코드입니다 :

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)도 놓칠 수 있습니다. 연속 번호 만 원합니까? for 루프 조건이 하나 씩 떨어져 있기 때문에 (-7 * 5) 또한 누락됩니다.

가 페이지를 초기화, 가장 직접적인 질문에 대답하기 (시작 * 끝) :

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)에, 당신은 추적해야합니다 2 개의 가장 큰 양수와 2 개의 가장 큰 음수. 다음과 같이 생각하십시오.

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); 
}