53. Maximum Subarray

주어진 숫자 배열 안에 연속된 부분 배열 중 가장 큰 값을 리턴하면 되는 심플 한 문제이다. 문제만 심플하지 생각할 것이 꽤 많은 문제였다. 

문제풀이를 하면서 다양하게 접근했다. 저기 주어진 예시들 은 길고 특별한 케이스이니 심플하게 만들어서 생각해보자.

[-3,2,3,-1]

뭐 있나 1번 부터 다 쓰자...

1번 인덱스 : 뭐 할 게 없다 그냥 리턴해줘야 한다...-3 

2번 인덱스 : [-3], [2] / [-3,2]  오 뭔가 느낌이 온다. 

3번 인덱스 : [-3], [2], [3]  / [-3,2], [2,3] / [-3,2,3] 왔다, 약간 dp 스럽게 풀어야 하는 건가 싶었다. 

 

현재 인덱스까지 진행된 것 중 버릴 거 버리면서 진행한다면  나쁘지 않은 효율이 나올 것 같았다. 

뭘 어떻게 버려 주어야 할까 고민하다가, 현재 진행 중인 값에 다음 값을 더해서 그 값이 다음값 보다 작다면? 뒤에 까지 다 더한 것은 쓸모가 없어진다.. -2 1 -3을 예로 들어보자 -2 1  => -1 인 상태에서 -3 을 더하면? -4인데 우리는 연속된 수를 구해야 하니 버리자 대신 저 앞에 까지 더해진 부분을 따로 기록을 해 두어야 할 것이다.

class Solution {
    public int maxSubArray(int[] arr) {
        if(arr.length == 1) return arr[0];
        int p1 = 0;
        int p2 = 1;
        int maxSum = arr[p1];
        int currentSum = arr[p1];
        while(p2<arr.length){
            int nextCur = currentSum + arr[p2];
            if(nextCur < arr[p2]){
                p1 = p2;
                currentSum = arr[p2];
            }else{
                currentSum = nextCur;
            }
            maxSum = Math.max(maxSum,currentSum);
            p2++;
        }
        return maxSum;
    }
}

 

오늘 two pointer 강의를 듣고 와서 그런가 엄청 비슷하게 푼 거 같은데 허점이 존재한다.... p1을 선언해 놓고 쓰지도 않는다......
고수들의 코드를 보자.

 

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

호 올리 몰리......  math.max를 이렇게 선언하면서 깔끔하게 for 반복문으로 해결해 버리는 아름다운 코드이다. 조금 더 디스커스를 둘러보면 Kadane's Algorithm 이란 글로 엄청 아름답게 써놓은 글이 있다. 따로 퍼오기 좀 그러니 링크를 첨부하겠다.

개괄적으로 설명을 하자면 위의 풀이법 그대로가 카 데인 알고리즘이다. 글 설명 10줄보다 그림 이 훨씬 보기 편하니 아래 링크로 이동해서 확인하면 더 도움 이 됩니다.
보러 가기

이 사람이 작성한 글에 의하면 어느 부분이던 합이 - 에 도달한다면, 이걸 계속 가지고 있을 의미가 없기 때문에 합을 0으로 초기화시켜준다고 한다.

-2 1 -3 4 -1 2 1 -5 4 (예시 1번)

i = 0  일 때 합은 -2 가 되고 , 최대 합은 -2 , 합이 0 보다 작기 때문에 현재 합은 0으로 초기화된다.

i = 1  일 때 합은 0+1(현재 합을 0 으로 초기화 시켜서 전 인덱스에서) 이되고, 합이 1 이된다 최대합은 1

i = 2 일 때 합은 1 -3 -2 가 되고 최대합은 1, 현재합은 0으로 초기화된다 왜 ?  0보다 작아서

i = 3 일때 합은 0+4 4 가되고 최대합은 4, 현재합은 4 가된다

이런 식으로 쭉쭉 이어나가면 된다. 위 링크에 더 자세히 설명되어 있으니 참고 바랍니다.!!

 

자세히 다시 보니 브루트 포스 에서 내가 느낀 그 디피 느낌이 이 카데인 알고리즘 이였다 그냥 디피라고 하면 될걸 왜 굳이 이름을 이렇게 붙이는지 다시보니 도둑이 집터는 문제랑 매우 유사하다고 생각된다...... 현재 합과, 현재 인덱스 중 큰 것, 또 맥스 값과 큰 것을 비교하는 법
왜 항상 모든 블로그 혹은 유튜브 비디오에서 항상 브루트 포스를 먼저 하라고 하는지 다시 한번 느끼는 문제였다..