CodeWars 일흔 세 번째 문제

Maximum subarray sum

public static int sequence(int[] arr) {
		
    int max = 0;

    for(int i = 0; i < arr.length; i++) {

        for(int j = 0; j < arr.length-i; j++) {
            int sum = 0;

            for(int x = j; x < j+i+1; x++) {
                sum+=arr[x];
            }

            if(max < sum) {
                max = sum;
            }
        }
    }

    return max;
}

• 전형적인 다이다믹 코딩 문제였다.
• 나는 문제 그대로 배열 갯수를 1,2,3… 씩 돌아가면서 최대값을 찾아 출력하는 것이었다.
• 그러나 Best 코드는 달랐다.
• 처음부터 하나씩 더해 가면서 0보자 작으면 버리고 크면 cur 변수에 넣는다. 그리고 이전에 더한 값 들 중에 찾아 놓은 max 값과 비교하여 크면 max에 저장 해놓고 다음 숫자로 간다.
• 코드는 이해가 가는데 왜 이게 되는지 정확히 이해가 안간다. 머리가 한계가 있나보다.

public static int sequence(int[] arr) {
    int cur = 0, max = 0;
    for (int i : arr) {
        cur = Math.max(0, cur + i);
        max = Math.max(max, cur);
    }
    return max;
}