[LeetCode - C] 53. Maximum Subarray

Maximum Subarray - LeetCode

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

---

Solution 1

 

어떻게 할까 고민하다가 무식하게 모든 경우의 수를 확인했다.

 

timelimit 걸려서 어떻게 줄여볼까 고민하다가

 

처음 생각난 방법이 합계가 0 미만이 되는 지점은 답이 될 수 없기에

 

sum < 0의 경우 다음 인덱스부터 확인하게 했다.

 

이후 제출에도 time limit이 걸리길래 확인해본 결과

 

양수로만 이루어진 크기가 큰 배열의 경우 너무 시간이 많이 걸린다는 것이다.

 

그래서 condition 추가해서 초기값 1에 음수가 됐을 때 0이 되게 하여

 

양수로만 이루어진 배열인가 확인을 했고,

 

다음 인덱스부터 모든 원소의 합을 더했을 때, 전의 배열보다 클일은

 

결코 발생하지 않기 때문에 바로 return 하게 했다.

 

static int answer;
static int sum;
static int condition;

void solution(int *nums, int numsSize, int i, int j);

int maxSubArray(int *nums, int numsSize)
{
    answer = nums[0];
    sum = 0;
    condition = 1;
    if (numsSize == 1)
        return (answer);
    solution(nums, numsSize, 0, 0);
    return (answer);
}

void solution(int *nums, int numsSize, int i, int j)
{
    if (i == numsSize)
        return 1;
    else if (j == numsSize || sum < 0)
    {
        if (answer < sum)
            answer = sum;
        sum = 0;
        if (condition)
            return 1;
        condition = 1;
        solution(nums, numsSize, i + 1, i + 1);
    }
    else
    {
        if (nums[j] < 0)
            condition = 0;
        sum += nums[j];
        if (answer < sum)
            answer = sum;
        solution(nums, numsSize, i, j + 1);
    }
}

---

Solution 2

 

더 쉬운 방법이 없을까 하여 다시 풀어봤다.

 

곰곰이 생각해보니 idx를 증가시켜가며 합을 구했을 때

 

sum이 음수라면 다음에 양수를 만났을 때 그 부분부터

 

다시 합을 구하면 됐다.

 

하지만 음수만 있는 배열일 때 처리를 어떻게 할지가 관건였는데

 

그냥 sum < 0일 때, nums [idx]가 sum보다 크면

 

다 해결이 될 거 같아 시도했는 데 성공했다.

int maxSubArray(int *nums, int numsSize)
{
    int answer;
    int sum;
    int idx;
    
    answer = nums[0];
    sum = 0;
    idx = 0;
    while (idx < numsSize)
    {
        if (sum < 0 && nums[idx] > sum)
            sum = 0;
        sum += nums[idx];
        if (sum > answer)
            answer = sum;
        idx++;
    }
    return answer;
}