Kadane&#s 알고리즘: Leetcode 최대 하위 배열

직관

2점 접근 방식을 통해 직관력을 키울 수 있습니다.

접근하다

maxSum과 maxTillNow라는 두 변수로 시작하겠습니다.

• 첫 번째 변수는 우리가 전체적으로 얻은 최대 합계를 배열에 저장합니다.

• 두 번째 변수는 현재 인덱스까지 도달한 최대 합계 값을 저장합니다. 배열에 음수 값이 있으므로 이 값은 변동되지만 maxSum < maxTillNow, maxSum을 업데이트합니다.

• 우리가 처리해야 할 마지막 경우는 인덱스가 0에 도달할 때까지의 최대 합계, 즉 maxTillNow < 0, 루프 끝에서 maxTillNow = 0을 재설정합니다.

복잡성

• 시간 복잡도: O(N)

• 공간 복잡도: O(1)

암호

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for(int i =0;i<nums.length;i++){
            maxTillNow+=nums[i];
            maxSum = Math.max(maxTillNow,maxSum);
            if(maxTillNow<0) maxTillNow = 0;
        }
        return maxSum;
    }
}

더 많은 솔루션을 보려면 GitHub 저장소: Git
Leetcode 프로필: Leetcode: devn007

위 내용은 Kadane&#s 알고리즘: Leetcode 최대 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!