질문

이 기사에서는 Leetcode의 '53. Maximum Subarray' 질문을 다룰 것입니다. 이 질문은 고전적인 문제입니다. Greedy Algorithm 문제입니다.

의문:

Given an integer array nu`ms, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.

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


질문 설명

이 질문의 등급은 보통입니다. 논쟁의 여지가 있지만 Divide and Conquer 기술을 사용하지 않는 경우 쉬운 질문으로 간주될 수 있습니다. Greedy Algorithm 기법을 사용하는 경우 이 문제는 쉬운 문제로 간주됩니다.

우리는 Kadane's Algorithm , Dynamic Programming 및 Greedy Algorithm 을 사용할 것입니다. Kadane's Algorithm은 하위 배열의 최대 합을 찾는 그리디 알고리즘입니다. 이것은 매우 간단한 알고리즘이며, 알지 못하는 사이에 이 알고리즘을 생각해내는 것이 전적으로 가능합니다. 매우 직관적입니다.

권장 지식(또는 배우려는 내용)

Array

Dynamic Programming

Greedy Algorithm

Kadane's Algorithm

Big O Notation

우리는 무엇을 알고 있습니까?

음수가 있을 수 있는 배열이 있고 주어진 하위 배열의 최대 합계를 찾아야 합니다.

어떻게 할 것인가:

하위 배열의 최대 합을 찾기 위해 Kadane's Algorithm을 사용할 것입니다. 즉, 현재 최대 하위 배열의 합을 수행하고 최대 하위 배열의 합보다 큰 숫자를 찾으면 하위 배열 값을 현재 숫자의 값으로 다시 시작하거나 하위 배열에 숫자를 계속 추가합니다.

새 최대 합계 배열이 현재 최대 합계보다 큰 경우 항상 추적합니다. 배열의 모든 숫자에 대해 이 프로세스를 반복합니다.

최대 합계 0부터 시작합니다. 길이가 1인 배열이 있을 수 있으므로 최대 합계는 그 자체입니다.

또한 -Infinity의 최대 하위 배열로 시작합니다. 이는 최대 하위 배열을 찾고 싶고 배열 내에서 하위 배열이 음수이므로 0의 하위 배열로 시작하고 싶지 않기 때문입니다.

빅오 표기법:

시간 복잡도: O(n) | 여기서 n은 배열의 길이입니다.

공간 복잡도: O(1) | 추가 메모리를 할당하지 않기 때문입니다.

이것이 개선될 수 있습니까?
음, 큰 O 표기법으로 NO! 그러나 Divide and Conquer 기술을 사용하여 속도를 향상시킬 수 있지만 선형 메모리를 사용하게 됩니다.

파이썬 솔루션

`

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

    subArraySum = float('-inf')
    maxSubSum   = nums[0]

    for num in nums:
        subArraySum = max(num, subArraySum + num)
        maxSubSum   = max(maxSubSum, subArraySum)

    return maxSubSum;

`

C++ 솔루션

`
class Solution {
public:
int maxSubArray(vector& nums) {
int subArraySum = -10000;
int maxSubSum = nums[0];

    for(const auto& num : nums) {   
       subArraySum = max(num + subArraySum, num);
       maxSubSum = max(maxSubSum, subArraySum);
    }

    return maxSubSum;
}

};
`

자바스크립트 솔루션

`
var maxSubArray = function (nums) {

let sub_array_sum = -Infinity; 
let max_sub_sum = nums[0]; 

for (const num of nums) {
    sub_array_sum = Math.max(num, sub_array_sum + num);
    max_sub_sum = Math.max(max_sub_sum, sub_array_sum);
}

return max_sub_sum;

};
`