[Leetcode] 53번 - Maximum Subarray

1. 문제 파악

• 문제 링크: https://leetcode.com/problems/maximum-subarray/description/
• 문제 정의: 배열 요소의 총합이 제일큰 subarray의 총합을 구해라.
• 시간복잡도: 입력크기가 10^5 이기 때문에 시간복잡도는 O(nlogn)이햐여야한다.

---

2. 문제 풀이

1. 문제 접근 과정

1. 처음에 subarray에서 최대값을 구하는 문제라 슬라이딩 윈도우로 접근했다.
2. 하지만 슬라이딩 윈도우로 풀리지 않았다.
3. 문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다'라는 것을 발견했다.
4. 그다음 그리디 문제처럼 최적의 해를 찾아서 푸는 알고리즘을 도출하였다.

2. 핵심 문제 풀이

문제의 핵심은 '배열을 순회하면서 총합이 양수이기만해도 최대값의 크기는 커진다' 라는 것이다.

따라서 문제를 풀기위해 다음의 이유로 두개의 변수가 필요하다.

• 배열을 순회하면서 요소값을 더할 총합 변수가 필요하다.
• 현재까지 더한 총합을 저장할 최대값 변수가 필요하다.

그러면 배열을 순회하면서 총합을 더한 후에, 기존 최대값보다 크면 최대값을 업데이트하면된다. 만일, 총합이 음수가 될때는 현재 더한 수를 더하면 최대값에서 멀어지게된다. 따라서 이전까지 업데이트된 최대값이 찾은 subarray의 최대값이다. 현재 총합의 음수를 야기한 다음 요소부터 새로운 subarray를 찾는것이다.

// 배열 순회하면서 최대값 업데이트
>
2 1 -1 -3 3 5
sum = 2
max = 2

// 2 1 -> 최대값 3 저장
  >
2 1 -1 -3 3 5
sum = 3
max = 3

// -3 순회시, 총합은 -1로 음수가 됨
// 이전에 찾았던 [2, 1]가 subarray의 최대값이다.
// 새로운 subarray를 찾기 위해서 총합의 변수를 0으로 초기화
        >
2 1 -1 -3 3 5
sum = 0
max = 3

// 새로운 subarray 찾기 시작
          >
2 1 -1 -3 3 5
sum = 3
max = 3

// 기존 최대값 3보다 큰 값 8을 가진 subarray 찾음
            >
2 1 -1 -3 3 5
sum = 8
max = 8

 

3. 입출력 케이스 도출 및 문제 풀이 도출 확인

조심해야될점은 입력 크기가 1개일때이다. 나의 경우에 그걸 고려하지 않고 구현해서 코드를 수정하였다.

 

4. 코드 구현

1. 총합과 최대값의 초기값을 첫번째 요소로 지정한다.
2. 배열을 순회한다.
3. 총합이 0보다 작으면 0으로 업데이트한다.
4. 총합에 배열 요소를 더한다.
5. 총합이 최대값 보다 크면 최대값을 업데이트한다.

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int n = nums.length;
        int max = sum;
        for (int i = 1; i < n; i++) {
            if (sum < 0) sum = 0;
            sum += nums[i];
            max = Math.max(sum, max);
        }
        return max;
    }
}

 

5. 복잡도

• 시간 복잡도
  • 배열 순회: O(N)
• 공간 복잡도
  • 추가 공간은 O(1)