[DP | Dynamic Programming] 카데인 알고리즘 Kadane's Algorithm

배열이 주어졌을때 maximum subarray 를 찾고자 한다.

 

본인의 경우 배열 내에서 가장 큰 값이 지속되는 구간을 찾아아 시작 인덱스와 종료 인덱스를 추출해야 했다.

 

• 시간 복잡도 O(N)

 

개념

• 각각의 최대 부분 합은 이전 최대 부분 합이 반영된 결과이다.
• 이전 인덱스가 가질 수 있는 최대 부분 합에 현재 인덱스 값을 더하면 현재 인덱스가 가질 수 있는 최대 부분 합을 구할 수 있음을 의미한다.

 

방법

• 각각의 인덱스 값은 이전 인덱스가 갖고 있는 최대 부분 합을 연장할지 아니면 자신의 값으로 초기화 할지 선택한다. 
• 연장
  • 이전 인덱스의 최대 부분합 + 현재 인덱스의 최대 부분 합 > 현재 인덱스 값
  • Math.max(A[i],A[i] + A[i-1])

 

 

 

적용 코드

    public AvailableScheduleResultResponse getResult(Long scheduleId,Long groupId){
        Map<LocalDateTime,Integer> resultMap = getResultMap(groupId,scheduleId);

        int temp_index=0;
        int maxSum =Integer.MIN_VALUE;
        int currentSum = Integer.MIN_VALUE;
        LocalDateTime maxStart=LocalDateTime.MIN;
        LocalDateTime maxEnd= LocalDateTime.MIN;
        LocalDateTime currentStart=LocalDateTime.MIN;
        LocalDateTime currentEnd=LocalDateTime.MIN;

        for (Map.Entry<LocalDateTime,Integer> entry : resultMap.entrySet()){

            if(temp_index==0){
                maxStart = maxEnd = currentStart = currentEnd = entry.getKey();
                maxSum=currentSum=entry.getValue();
                temp_index++;
            }

            if(entry.getValue().compareTo(resultMap.get(currentEnd))==0 ) {
                currentEnd = entry.getKey();
            }else{
                currentSum = entry.getValue();
                currentStart = entry.getKey();
                currentEnd = entry.getKey();
            }

            if(currentSum>=maxSum){
                maxSum = currentSum;
                maxStart = currentStart;
                maxEnd = currentEnd;
            }
        }

        return AvailableScheduleResultResponse.builder()
                        .availableStartTime(maxStart)
                        .availableEndTime(maxEnd)
                        .availableNum(maxSum)
                        .build();
    }