지난번 풀이에서 시간복잡도가 O(n₂)가 되어서 찝찝했는데,
다시 풀어보도록 하자.

Identifying the Problem

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

Organizing thoughts

간단한 아이디어만 소개하면

0. 초기 max 값을 nums[0] 으로 초기화하고, 누적합은 0으로 초기화한다.,

1. 배열을 탐색하며 누적 합을 구하다

2. 누적합이 0이 되면 0으로 초기화 한다.

3. 만약 누적합이 max 값보다 크면 max에 누적값을 대입한다.

4. max 값을 리턴한다. 

Sourcecode

int maxSubArray(int* nums, int numsSize){

    int cur_sum = 0;
    int max = nums[0];
        
    for(int i = 0 ; i<numsSize; i++)
    {
        if(cur_sum < 0) cur_sum = 0;
        
        cur_sum += nums[i];
        
        if(cur_sum > max) max = cur_sum;  
    } 
    
    return max;
}

Mistake

누적합의 초기값과 max값의 초기값을 헷갈렸다.

핑계를 대자면 오늘 근무가 너무 힘들었다.