Lesson 9 - MaxSliceSum

자세한 문제는 여기서 확인하시면 됩니다.

 

문제는 (P,Q)일 때 0<=P<=Q<N 으로 연속된 값들의 합이 가장큰 경우를 찾는 문제입니다.

 

이 문제는 Kadane's algorithm 을 사용해서 푸는 문젭입니다.(Kadane's algorithm의 자세한 내용은 다음기회에..)

 

fun solution(A: IntArray): Int {
  
    if( A.size == 1){
        return A[0]
    }
    var max_1 = A[0]
    var max_2 = A[0]

    for(i in 1 until A.size){
        max_1 = Math.max(A[i],max_1+A[i])
        max_2 = Math.max(max_2,max_1)
    }
    return max_2
}

max_1을 통하여 array의 덧셈들을 체크하고 max_2로 그 덧셈들중 최대값을 반환합니다.