[코딜리티] - Lesson 9.MaxSliceSum

안녕하세요 남갯입니다.

public static int solution(int[] A) {
    // write your code in Java SE 8

    int maxEnding = 0;
    int maxSlice = Integer.MIN_VALUE;
    int maxValue = Integer.MIN_VALUE;
    for (int a : A) {
        // a> 0이면서 maxEnding or maxSlice 0보다 작다는건 음수값에서 양수값인 값이 나왔을때
        if ((maxEnding < 0 || maxSlice < 0) && a > 0) {
            maxValue = maxSlice;
            maxSlice = 0;
            maxEnding = 0;

        }
        maxEnding = Math.max(Integer.MIN_VALUE, maxEnding + a);
        maxSlice = Math.max(maxSlice, maxEnding);
        if (a > maxValue) {
            maxValue = a;
        }
        if (maxSlice > maxValue) {
            maxValue = maxSlice;
        }
    }
    return (maxValue > maxSlice) ? maxValue : maxSlice;
}

맨 마지막 값이 나오지 않음

https://app.codility.com/demo/results/training8BHT5Q-GCD/

오버플로우 방지

public static int solution(int[] A) {
    // write your code in Java SE 8
    long maxEnding = 0;
    long maxSlice = Integer.MIN_VALUE;
    long maxValue = Integer.MIN_VALUE;
    for (int a : A) {
        // a> 0이면서 maxEnding or maxSlice 0보다 작다는건 음수값에서 양수값인 값이 나왔을때
        if ((maxEnding < 0 || maxSlice < 0) && a > 0) {
            maxValue = maxSlice;
            maxSlice = 0;
            maxEnding = 0;

        }
        maxEnding = Math.max(Integer.MIN_VALUE, maxEnding + a);
        maxSlice = Math.max(maxSlice, maxEnding);
        if (a > maxValue) {
            maxValue = a;
        }
        if (maxSlice > maxValue) {
            maxValue = maxSlice;
        }
    }
    return (maxValue > maxSlice) ? (int)(maxValue) : (int)(maxSlice);
}

https://app.codility.com/demo/results/trainingRH6AKH-K6D/