Maximum Subarray[Array,Divide and Conquer,Dynamic Programming]

https://leetcode.com/problems/maximum-subarray/description/

Given an integer array nums, find the 

subarray

 with the largest sum, and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

1. Python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = nums[0]
        curr_max = nums[0]

        for num in nums[1:]:
            curr = max(num, curr+num)
            curr_max = max(curr_max,curr)
        return curr_max

뭔가 깔끔하긴 한데, Recursion을 쓰진 않았다.

이게 바로 카데인 알고리즘이구만 .. Kadanes Algorithm으로 DP를 쓴 것이다.

이 코드에서 사용한 방법은 **카데인 알고리즘(Kadane's Algorithm)**으로, 이는 **동적 계획법(Dynamic Programming)**을 사용한 해결 방법입니다. 동작 방식: curr는 현재 위치에서 끝나는 부분 배열 중 최대 합을 저장합니다. curr_max는 지금까지 본 부분 배열 중 최대 합을 저장합니다. 이 알고리즘은 배열을 한 번 순회하며 각 단계에서 두 가지 선택을 합니다: 현재 숫자 num을 포함하는 새로운 부분 배열을 시작할지. 현재까지의 최대 부분 배열에 num을 더할지. 매 반복마다 curr는 현재까지의 최대 부분 배열 합을 갱신하며, curr_max는 전체 배열에서의 최대 부분 배열 합을 추적합니다. 핵심 아이디어: 각 위치에서 최대 부분 배열 합을 갱신하는 방식으로, 이전에 계산된 결과를 재활용해 효율적으로 문제를 해결합니다. 시간 복잡도는 **O(n)**로, 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다. 이 방식은 분할 정복과 달리 추가적인 공간이나 재귀 호출이 필요 없으며, 메모리 사용도 **O(1)**입니다.

 

아.. divde conquer 연습하기엔 너무 빡세다.

다른 문제를 더 찾아보자.

 

참고로 D & C 코드는 아래와 같다.

 

def max_crossing_sum(arr, left, mid, right):
    # 왼쪽 부분에서 최대 합을 계산
    left_sum = float('-inf')
    current_sum = 0
    for i in range(mid, left - 1, -1):
        current_sum += arr[i]
        if current_sum > left_sum:
            left_sum = current_sum

    # 오른쪽 부분에서 최대 합을 계산
    right_sum = float('-inf')
    current_sum = 0
    for i in range(mid + 1, right + 1):
        current_sum += arr[i]
        if current_sum > right_sum:
            right_sum = current_sum

    # 중앙을 가로지르는 최대 합을 반환
    return left_sum + right_sum

def max_sub_array_divide_and_conquer(arr, left, right):
    if left == right:
        # 배열이 한 개의 요소만 있을 때 그 값을 반환
        return arr[left]

    mid = (left + right) // 2

    # 3가지 경우를 각각 재귀적으로 구함
    left_sum = max_sub_array_divide_and_conquer(arr, left, mid)
    right_sum = max_sub_array_divide_and_conquer(arr, mid + 1, right)
    cross_sum = max_crossing_sum(arr, left, mid, right)

    # 가장 큰 값을 반환
    return max(left_sum, right_sum, cross_sum)

def max_sub_array(arr):
    return max_sub_array_divide_and_conquer(arr, 0, len(arr) - 1)

 

2. C++

# C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maxCrossingSum(vector<int>& arr, int left, int mid, int right) {
    int left_sum = INT_MIN;
    int current_sum = 0;

    // 왼쪽 부분에서 최대 합 계산
    for (int i = mid; i >= left; i--) {
        current_sum += arr[i];
        if (current_sum > left_sum) {
            left_sum = current_sum;
        }
    }

    int right_sum = INT_MIN;
    current_sum = 0;

    // 오른쪽 부분에서 최대 합 계산
    for (int i = mid + 1; i <= right; i++) {
        current_sum += arr[i];
        if (current_sum > right_sum) {
            right_sum = current_sum;
        }
    }

    // 중앙을 가로지르는 최대 합 반환
    return left_sum + right_sum;
}

int maxSubArrayDivideAndConquer(vector<int>& arr, int left, int right) {
    if (left == right) {
        // 배열이 하나의 요소만 있을 때 그 값을 반환
        return arr[left];
    }

    int mid = (left + right) / 2;

    // 3가지 경우에 대해 각각 최대 합을 계산
    int left_sum = maxSubArrayDivideAndConquer(arr, left, mid);
    int right_sum = maxSubArrayDivideAndConquer(arr, mid + 1, right);
    int cross_sum = maxCrossingSum(arr, left, mid, right);

    // 세 경우 중 가장 큰 값을 반환
    return max({left_sum, right_sum, cross_sum});
}

int maxSubArray(vector<int>& arr) {
    return maxSubArrayDivideAndConquer(arr, 0, arr.size() - 1);
}