Striver의 SDE 시트 여정 - #4 Kadane의 알고리즘

안녕하세요👋개발자 여러분,

이전 게시물에서 우리는 문제를 해결하고 이해했으며 이 게시물에서는 다음 Kadane의 알고리즘을 다룰 것입니다.

#4 Kadane의 알고리즘

이 문제에서 우리는 정수 배열nums을 제공했으며, 합이 가장 큰 연속 하위 배열(적어도 하나의 숫자 포함)을 찾고 그 합을 반환합니다.

Example 1:

입력: nums = [-2,1,-3,4,-1,2,1,-5,4]
출력: 6설명: [4,-1,2,1]의 합이 가장 큽니다 = 6.

Example 2:

입력: nums = [1]
출력: 1

해결책

우리는 kadane의 알고리즘을 사용하여 이 문제를 쉽게 해결할 수 있습니다.
Kadane의 알고리즘을 단계별로 논의하겠습니다.

1단계는 3개의 int 변수sum = 0 , max = nums[0] , arrSize = nums.length 를 초기화합니다.

2단계는 i = 0에서 arrSize까지 루프를 실행합니다.

1. sum = sum + nums[i].
2. if sum > max then max = sum.
3. if sum < 0 then sum = 0.

3단계 반품max
4단계 끝
sum = 0인 경우 sum < 0를 다시 초기화하는 이유는 무엇입니까?
음수 합계는 최대 합계에 기여하지 않으므로 합계를 0으로 다시 초기화하고 다음 요소에서 추가를 시작하는 것이 좋습니다.

자바에서 이 알고리즘을 코딩하기 전에 이 알고리즘을 더 잘 이해하기 위해 이 이미지를 살펴보십시오.

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;

        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];

            if(sum > max){
                max = sum;
            }

            if(sum < 0) {
                sum =0
            }
        }

        return max;

}
}

하지만 어떻게? 우리가 알 수 있을까요,

최대 하위 배열의 길이

최대 하위 배열의 시작 및 끝 인덱스

최대 하위 배열의 요소

따라서 이를 위해 최대 하위 배열의 시작 및 마지막 인덱스 번호를 저장하는 int 변수firstIndex 및 lastIndex를 두 개 더 만든 다음 2단계에서 일부 수정을 수행할 수 있습니다.

step-2 run a loop from i = 0 to arrSize.

1. sum = sum + nums[i].
2. if sum > max then max = sum,lastIndex = i.
3. if sum < 0 then sum = 0, firstIndex = i+1.

firstIndex 및 lastIndex 변수를 사용하여 이제 다음 질문에 답할 수 있습니다.

하위 배열의 길이입니다.subArrSize = lastIndex - firstIndex

하위 배열의 시작 및 끝 인덱스입니다.firstIndex 및 lastIndex 변수

를 사용하여

최대 하위 배열의 요소입니다.firstIndex에서 lastIndex까지 이동하면

요소를 찾을 수 있습니다.

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int max = nums[0];
        int arrSize = nums.length;
        int firstIndex = 0,lastIndex = 0;

        for(int i=0; i < arrSize; i++){
            sum = sum + nums[i];

            if(sum > max){
                max = sum;
                lastIndex = i;
            }
            if(sum < 0) {
                sum =0;
                firstIndex = i + 1;
            }
        }

        return max;

}
}

Time Complexity⏱️

0에서 arrSize까지 for 루프를 실행합니다.
따라서 O(arrSize)는 시간 복잡도가 됩니다.

Space Complexity⛰️

알고리즘이 추가 공간을 사용하지 않으면 O(1)이 공간 복잡도가 됩니다.

이 기사가 마음에 들면 댓글 섹션에서 알려주십시오.
게시물에 잘못된 것이 있으면 수정해 주세요.
제 글을 읽어주셔서 감사합니다.