<aside> 💬 lv1, 탐색, 동적 프로그래밍, 카데인 알고리즘

연속 수열의 최대합

문제 설명

정수로 이루어진 배열이 주어집니다. 이 배열에서 연속된 부분 수열의 합 중 최대값을 찾는 코드를 작성해주세요.

제한 사항

• 배열의 길이는 최소 1에서 최대 100까지입니다.
• 배열의 각 요소는 -100 이상 100 이하의 정수입니다.
• 연속된다는 것은 배열안에 인덱스가 연속된다는 의미입니다.

입출력 예

입출력 설명

첫 번째 예시에서 가장 큰 부분 수열 합은 [3, 4, -1, 2, 1]으로, 합계는 9입니다. 두 번째 예시에서는 [4, -1, -2, 1, 5]의 부분 수열 합이 최대이며, 합계는 7입니다.

</aside>

😺 풀이 1. 카데인 알고리즘 사용

def solution(data):
    if not data: **#1 기본 조건 확인**
        return 0

    max_sum = current_sum = data[0] **#2 초기값 설정**

    for num in data[1:]:
        print(num)
        **#3 연속된 수의 합 계산 및 최대값 갱신**
        # 현재 값인 num과 현재 위치까지의 최대합과 num을 더한 값 중
        # 큰 값을 현재 위치까지의 최대합으로 설정합니다. 
        # 이전까지 더한 값이 음수인 경우 '현재 값'부터 다시 더하기 시작합니다.
        current_sum = max(num, current_sum + num)
        
        # 이렇게 설정된 현재 위치까지의 최대합을 최대 합과 비교하여 
        # 더 큰 값을 최대 합으로 설정합니다.
        max_sum = max(max_sum, current_sum)
        print("-----------")

    return max_sum **#4 최종 최대합 반환**

단계별 풀이 전략

1. 기본 조건 확인

   입력 리스트가 비어있는 경우, 최대합은 0입니다.

2. 초기값 설정

   리스트의 첫 번째 원소를 최대합(max_sum) 및 현재까지의 최대합(current_sum)으로 초기화합니다.

3. 연속된 수의 합 계산 및 최대값 갱신

   리스트의 두 번째 원소부터 순회하며, 현재 원소(num)를 포함하는 연속된 수의 합을 계산합니다. current_sum을 num과 current_sum + num 중 더 큰 값으로 갱신합니다.

   이는 num을 새로운 시작점으로 삼거나 기존 수열에 추가하는 것과 동일합니다. max_sum을 현재까지의 max_sum과 갱신된 current_sum 중 더 큰 값으로 갱신합니다.

4. 최종 최대합 반환

   모든 원소를 순회한 후, 계산된 최대합을 반환합니다.

알아둬야 할 개념

카데인 알고리즘

• 개념: 카데인 알고리즘은 연속된 수열 중 최대합을 효율적으로 찾는 방법입니다. 현재까지의 최대 부분합을 계속해서 갱신하며, 전체 배열을 단 한 번만 순회하여 최대 부분합을 찾아냅니다. 이는 동적 프로그래밍의 한 예로 볼 수 있습니다.

  def findMaxSubArraySum(nums):
      currentSum = maxSum = nums[0]
      for num in nums[1:]:
          currentSum = max(num, currentSum + num)
          maxSum = max(maxSum, currentSum)
      return maxSum
  

max()함수

• 기본 형태: max(a, b)

• 개념: Python의 내장 함수 중 하나로, 주어진 두 인자 중 더 큰 값을 반환합니다. 이 함수는 다양한 상황에서 최대값을 쉽게 찾기 위해 사용됩니다.

  # 두 수 중 더 큰 수 반환
  print(max(10, 20))  # 출력: 20
  

풀이 2. 브루트 포스를 이용한 최대 부분 배열 합 계산

def solution(data):
    l = [] **#1 모든 연속 부분 배열 생성**
    for i in range(len(data)):
        for j in range(len(data)):
            if j > i:
                l.append(data[i:j])

    max_value = float('-inf') # 초기 최대값 설정

    for num in l: **#2 최대 부분 배열 합 계산**
        if sum(num) > max_value:
            max_value = sum(num)

    return max_value # 최대 부분 배열 합 반환

단계별 풀이 전략