최대 하위 배열 합계🤖

하위 배열 질문은 배열을 통해 반복해야 하지만 도전적으로 만들 수 있는 몇 가지 추가 논리/조건이 있습니다. 그러나 이 솔루션은 몇 가지 조건만 있으므로 이해하기 쉬울 수 있다고 생각합니다.

이 문제는 배열에서 연속 숫자의 가장 큰 합을 구하도록 요청합니다.

let nums = [ -3, 1, -4, 1, 2, 1]
// solution -> 4 ( from 1,2,1 subarray)

이 경우 접근 방식은 이전 요소의 숫자 합계를 누적하는 것을 포함하며 현재 요소를 포함하는 새 합계와 이전 합계 사이에서 가장 높은 합계를 확인합니다. 따라서 첫 번째 하위 배열sum은 다음 요소의 합계를 누적하는 데 사용되는 배열의 첫 번째 값일 뿐입니다.

sum = nums[0]

기본 경우에는 더 이상 반복할 요소가 없으므로 루프를 건너뛰어 첫 번째 요소만 반환합니다.

그러나 반복할 요소가 더 있으면 배열이 끝날 때까지 두 번째 요소(인덱스 1)부터 시작합니다. 인덱스 1에서 시작하면 현재 요소를 첫 번째 루프의 이전 요소와 비교할 수 있습니다.

if (nums[i - 1] > 0) { 
// only if the previous accumulation sum (previous element) is positive
  nums[i] += nums[i - 1]; // accumulate current element by adding last to current
}

nums[i] 와 nums[i-1] 에서 이전 요소의 합을 누적한 후 현재 합( nums[i] )을 지금까지 가장 높은 합( sum )과 비교할 수 있습니다.

sum = Math.max(nums[i], sum)

첫 번째 루프sum에서 배열의 첫 번째 요소가 되고 이후에는 지금까지 찾은 가장 높은 합이 됩니다.

전체 알고리즘:

const maxSubArray = (nums) => {
    let sum = nums[0];

    for (let i = 1; i < nums.length; i++) { 
// starts at index one to compare and acculumate 

        if (nums[i - 1] > 0) { 
// if the accumulation sum is positive
            nums[i] += nums[i - 1]; 
// accumulate current element by adding current to last
        }

        sum = Math.max(nums[i], sum); 
        // save highest number either current sum of previous higher sum
    }
    return sum;
};

검토하기 위해 배열을 반복하고 이전에 누적된 합계가 양수인지 확인하고 true이면 현재 요소를 추가하는지 확인합니다. 마지막으로 전체 배열을 반복한 후 현재 합계를 Math.max로 지금까지 가장 높은 합계와 비교하여 답을 sum 반환합니다.

어떤 생각/아이디어든지 자유롭게 연락하세요!