Codility Lesson 09 - MaxSliceSum(JAVA)

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/

MaxSliceSum coding task - Learn to Code - Codility

 

문제

- N개의 정수들로 이루어진 A배열이 있다.

- (P, Q)는 ) 0 ≤ P ≤ Q < N 범위에서 A[P] + A[P+1] + ... + A[Q]를 의미하는 부분배열의 합이다.

- 부분배열의 합중 최대값을 찾아라

- 예시 : A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

 

제한조건

• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be an integer within the range [−2,147,483,648..2,147,483,647].

N은 1~ 1,000,000 사이의 정수이다.

A 배열의 각각의 원소는 -1,000,000 ~ 1,000,000사이의 수이다.

결과값은 -2,147,483,648 ~ 2,147,483,647사이의 수이다.( Integer의 범위를 넘어가지 않음을 의미 )

 

풀이

- A배열이 제한조건 1에 따라 빈배열이 없으므로 예외처리 없이 진행.

- int maxVal = maxLocal = 0으로 초기화 해준다.( maxValue는 부분배열 합의 최대값을 maxLocal은 현재까지의 부분배열의 합 중 큰 값을 셋팅한다 )

- A배열의 크기만큼 for문을 순회하면서 로직을 실행한다.

- 해당 인덱스에 해당하는 A배열의 값을 가져오고( A[i] ) maxLocal = maxLocal + A[i]으로 누적합을 구한다.

- 이 때 maxLocal 의 값이 음수인 경우에는 maxLocal 변수를 0으로 교체한다.

- maxLocal 과 maxVal를 비교하여 큰 값을 maxVal에 넣는다.

 

예상 시간복잡도 : O(N) - for문을 전부 순회

 

소스코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int maxVal = 0; // 3 5 5 5 5
        int maxLocal = 0;   // 3 5 0 4 4

        for( int i=0; i<A.length; i++ ){
            maxLocal = maxLocal + A[i];
            if( maxLocal < 0 ){
                maxLocal = 0;
            } 

            if( maxVal < maxLocal ) maxVal = maxLocal;

        }

        return maxVal;
    }
}

 

위의 소스코드대로 실행하면, 음수인 경우가 해당 되지 않는다( 최대값이 무조건 양수일 경우만 있는 것이 아니므로 문제의 취지와 맞지 않다..)

 

풀이 수정

- int maxVal = Integer.MIN_VALUE로 초기화한다( maxVal가 0으로 초기화 되어 있으면 maxLocal과 비교하는 로직에서 음수가 무시된다.. )

- tmpSum = maxLocal + A[i] 임시 변수를 둔다.

- A[i]와 tmpSum을 비교하여 큰 수를 maxLocal에 넣는다.

- maxVal과 maxLocal을 비교하여 큰수를 maxVal에 넣는다.

 

수정 코드

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int maxVal = Integer.MIN_VALUE; // 3 5 5 5 5
        int maxLocal = 0;   // 3 5 0 4 4

        for( int i=0; i<A.length; i++ ){
            int tmpSum = maxLocal + A[i];

            maxLocal = tmpSum < A[i]?A[i]:tmpSum;

            if( maxVal < maxLocal ) maxVal = maxLocal;

        }

        return maxVal;
    }
}

항상 코너케이스를 생각하며 코딩테스트에 임해야한다..