[Leetcode] 152. Maximum Product Subarray

Identifying the Problem

주어진 수열에서 가장 큰 부분 곱을 리턴한다.

Organizing thoughts

O(n²) 인 알고리즘으로 금방 푸는 문제지만, 다른 방법으로 어떻게 풀 지 

생각해봤는데 도저히 모르겠어서 정답을 참고했다.

코드는 의외로 간단하다.

 

수열이 다 양수면 상관이 없지만, 음수가 나오거나 0이 나오는 순간 굉장히 복잡해진다.

이런 것을 막기 위해 max 값과 min 값을 나눠서 구하는데

max 값은 왜 구하는지 직관적으로 이해가 가지만,

min 값은 왜 구하는지 도저히 이해가 안가서 Excel 로 수를 적어가니 알게 되었다.

최소값에 음수를 곱하는 순간 그 값이 최대값이 되기 때문이다.

최대값에만 메달려 있다보니, 이 생각을 미쳐 못한 것 같다.

따라서 최대값과 최소값은 탐색하는 1) 현재값 2) 가장 큰 곱과 현재값의 곱 3) 가장 작은 곱과 현재값의 곱 중에서 

선별된다.

 

Sourcecode

int max(int a,int b);
int min(int a,int b);


int maxProduct(int* nums, int numsSize)
{
    int max_val = nums[0];
    int min_val = nums[0];
    int ans = nums[0];
    int x,y;
        
    for(int i=1;i<numsSize;i++)
    {
        x = max(max(nums[i], max_val * nums[i]), min_val * nums[i]);  
       
        y = min(min(nums[i], max_val * nums[i]), min_val * nums[i]); 

        max_val = x;
        min_val = y;
        
        ans = max(max_val, ans); 
        
        
    }
    
    return ans;
}

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
    
}
int min(int a,int b)
{
    if(a<b) return a;
    else return b;
    
}

Mistake

• max 값을 구하고 그 값을 min을 구하는 과정에 바로 넣어서 값이 이상하게 나오는 경우가 있었다. 
  코드의 흐름, 순서를 파악하는 것을 잊지말자.

New things learned

수열관련한 문제를 풀 때, 최소 최대를 이용하는 경우가 많은 것 같다.

심층적으로 생각해보자.