[LeetCode] Java - Maximum Subarray

 

4월 1일부터 4월 30일까지 진행하는 LeetCode 30 Day Challenge를 하면서 문제 푸는 방법에 대한 정리하는 글입니다.

 

- 문제 

연속된 합이 Max가 되는 구간의 합을 구하는 문제입니다.

문제에서 예를 들면 4, -1, 2, 1 의 연속된 구간의 합이 max가 되기 때문에 6이 답이 됩니다.

 

- 풀이

 

Follow up을 확인하면 시간복잡도가 O(n)으로 해결되는 문제임을 알 수 있습니다.

그래서 어떻게 하면 시간복잡도가 O(n)이 될 수 있을지 고민해봤어요.

O(n)이 되려면 주어진 숫자 만큼 for문을 1회 실행 한다고 생각하면 됩니다.

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

이 문제는 sum을 담는 변수를 두개 선언합니다.

 

currentSum : 현재 index와 max 값이 였던 index부터 sum을 구했던 숫자 중 가장 큰 값을 저장하는 변수

maxSum : 현재 index 까지 max 값.

 

currentSum이 핵심적인 변수 입니다.

[-2, 1, -3, 4, -1, 2, 1, 5, -4] 로 예를 들어보겠습니다.

 

index = 1 일때

currentSum = max(1, -2 + 1) = 1;
maxSum = 1

index가 1일때 currentSum은 1과 -2+1 값 중 max 값을 선택합니다.

그러면 currentSum은 1이 되고 자동적으로 index는 1부터 시작한다고 생각해도 됩니다.

그리고 maxSum은 1이 되겠죠.

index = 2 일때

currentSum = max(-3, 1 + -3) = -2;
maxSum = 1

index가 2일때는 curretSum은 -2가 되고 maxSum은 index가 1일때 값인 1이 됩니다.

index = 3 일때

currentSum = max(4, 4 + -2) = 4;
maxSum = 4

index = 3 일때

currentSum은 4가 되고 maxSum은 4가 됩니다.

이렇게 되면 index=3일때 부터 더하는 값이 max 값으로 설정되어 진행되겠죠.

 

이렇게 어느 지점 부터 합을 시작해도 되는지 관리 하지 않아도 위 알고리즘을 이용하면 자동으로 관리 하게 됩니다.

그리고 시간복잡도는 O(n)가 되죠.

 

이렇게 3일차도 재미있는 알고리즘 한번 공부해보았습니다.

오늘도 간단하지만 실제 개발에서도 사용될 수 있는 고민을 한번 해보게 되었네요.

 

오늘의 공부는 여기까지.