LeetCode) 53. Maximum Subarray

배열에서 나올 수 있는 최대 합은 얼마인가?를 구하는 문제.

Language: java

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

이게 내가 푼 코드인데 ... 이상하게 자꾸 runtime 초과 에러가 나왔다.
(물론 컴퓨터가 더 정확하기 때문에 이상하지는 않겠지만 ...ㅠ_^)
대체 뭐가 문젤까해서 시간을 들여도 도저히 해결되지 않아서 ...

결국 또 구글링의 힘을 빌렸다.

//다른 사람의 풀이, Math.max()가 뭔지 알아보자
class Solution{
    public int maxSubArray(int[] nums){
        int sum = 0;
        int maxSum = nums[0];

        for(int n : nums) {
            sum = Math.max(n, sum + n);
            maxSum = Math.max(maxSum, sum);
        }
        return maxSum;
    }
}

수많은 글을 봤는데, 다들 Math.max()라는 것을 이용하여 풀었다는 공통점이 있었다. Math.max()란 두 인수를 비교하여 더 큰 것을 return하는 함수였다.

내가 아직 모르는 것이 투성이구나,를 깨닳는 문제였음!