[Leetcode] 53. Maximum Subarray

Identifying the Problem

주어진 nums 배열에서 가장 큰 부분합을 찾아 return 한다.

 

제한조건

• 1 <= nums.length <= 3 * 10^4
• -105 <= nums[i] <= 105

Organizing thoughts

계단식으로 가능한 모든 sum을 구해 가장 큰 경우를 return 한다.

계단식이라 함은 

0번 ~ 1번 합

0번 ~ 2번 합

0번 ~ 3번 합 ...

n-1번 ~ n번 합 까지 다 구하는 것을 말한다.

 

Sourcecode

int maxSubArray(int* nums, int numsSize){
 

if(numsSize == 1) return *nums; //size가 1인경우 전체합과 부분합이 같으므로 그대로 return
    
    
int sum = 0;
int max = -100000; //제한 조건에 따라 가장 작은 max값을 -100000로 초기화하였다.
int max_f = -100000;
 
for(int i=0; i<numsSize; i++)
{
    
    
    
    for(int k=i; k<numsSize;k++)
    {
     sum+= *(nums+k);
     if(sum>max) max =sum; //i번째에서 가능한 최대 max 값을 찾아 max 에 넣는다.
         
    }
    
    if(max > max_f) max_f=max; //전체 중에서 가장 큰 max 값을 max_f 에 대입한다.
    
    sum = 0; //sum과 max을 초기화한다.
    max = -100000; 
}    
    
    
    return max_f;
}

Mistake

시간복잡도 O(n) 제한 조건을 어겼다.

분할 정복 알고리즘으로 다시 풀어보도록 하겠다. 

 

알고리즘 형태, 자료구조 등 배울 것이 태산이다. 

조건에 부합하지 않더라도, 최대한 스스로 풀 수 있는 방법에 집중할 것이다.

New things learned

 

[알고리즘] Divide and Conquer (분할정복)