코딩테스트 #1

매일프로그래밍을 구독하게 되었습니다. (https://mailprogramming.com/)

매주 월요일날 간단한 코딩문제가 메일로 전송됩니다. 아직까진 무료이나.. 조만간 유료로 전환된다고 하네요..?

항상 연습해야지 공부해야지 하고 중간에 포기를 많이했었는데, 일주일에 한번와서 고민도 해보고 코딩연습도 하고 좋은 것 같네요 ㅎㅎ

#1

정수 배열(int array)가 주어지면 가장 큰 이어지는 원소들의 합을 구하시오. 단, 시간복잡도는 O(n).

예제}

Input: [-1, 3, -1, 5]

Output: 7 // 3 + (-1) + 5

Input: [-5, -3, -1]

Output: -1 // -1

Input: [2, 4, -2, -3, 8]

Output: 9 // 2 + 4 + (-2) + (-3) + 8

    

    public int solution(int[] array) {
        int curSum = array[0];
        int maxSum = array[0];
        int length = array.length;

        for(int i=1; i< length; i++) {
            // 더한 값이 더 작을시, 다음 인자를 처음으로 하여 인자를 더해 간다
            curSum = Math.max(curSum + array[i], array[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        
        return maxSum;
    }