LeetCode 명상: 최대 제품 하위 배열

최대 제품 하위 배열에 대한 설명은 다음과 같습니다.

정수 배열 nums가 주어지면 가장 큰 곱이 있는 하위 배열을 찾고 그 곱을 반환합니다.

답변이 32비트 정수에 맞도록 테스트 사례가 생성되었습니다.

예:

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

Input: nums = [-2, 0, -1]
Output: 0
Explanation: The result cannot be 2, because [-2, -1] is not a subarray.

---

이제 무차별 접근 방식을 사용하여 중첩 루프로 문제를 해결할 수 있습니다.

결국 최대값을 얻어야 하므로 먼저 배열의 최대값을 알아봅시다.

let max = Math.max(...nums);

그런 다음 각 숫자를 살펴보면서 계속해서 나머지 숫자와 곱하여 합계를 만들 수 있습니다. 이 합계가 최대값보다 크면 다음과 같은 새로운 값을 가리키도록 최대값을 업데이트할 수 있습니다.

for (let i = 0; i < nums.length; i++) {
  let total = nums[i];
  for (let j = i + 1; j < nums.length; j++) {
    total *= nums[j];
    if (total > max) {
      max = total;
    }
  }
}

마지막에는 max. 따라서 최종 솔루션의 첫 번째 시도는 다음과 같습니다.

function maxProduct(nums: number[]): number {
  let max = Math.max(...nums);
  for (let i = 0; i < nums.length; i++) {
    let total = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      total *= nums[j];
      if (total > max) {
        max = total;
      }
    }
  }

  return max;
}

시간과 공간의 복잡성

시간 복잡도는 $오(n^2)$O(n2) 중첩 루프가 있으므로 반복하는 각 숫자에 대해 각 숫자에 대해 상수 연산을 수행합니다.
공간 복잡도는 $O(1)$O(1) 추가 저장용량이 필요하지 않기 때문입니다.

다시 한번 말씀드리지만 이것은 단지 무차별적인 시도일 뿐입니다. 그럼 심호흡을 한 번 하시고, 또 다른 해결 방법을 살펴보겠습니다.

---

이 새로운 솔루션의 아이디어는 배열의 각 숫자를 살펴볼 때 최대값과 최소값에 대해 서로 다른 두 값을 유지하는 것입니다. 그 이유는 곧 살펴보겠지만 음수 값을 처리하기 때문입니다.

먼저 이러한 값을 초기화하는 것부터 시작하겠습니다. currentMax, currentMin 및 결과가 있으며, 이들 모두 처음에는 배열의 첫 번째 값을 가리킵니다.

let currentMax = nums[0];
let currentMin = nums[0];
let result = nums[0];

이제 두 번째 숫자부터 시작하여 각 값을 반복하면서 현재 최대값과 현재 최소값은 물론 결과(최종 최대값이 됨)도 업데이트하겠습니다.

for (let i = 1; i < nums.length; i++) {
  currentMax = Math.max(nums[i], nums[i] * currentMax);
  currentMin = Math.min(nums[i], nums[i] * currentMin);

  result = Math.max(result, currentMax);
}

그러나 그 전에, 그렇게만 하면 어떤 일이 일어날 수 있는지 예를 들어 보겠습니다.

우리 배열이 [-2, 3, -4]라고 가정해 보겠습니다. 처음에는 currentMax와 currentMin이 모두 -2입니다. 이제 currentMax를 업데이트하기 위해 두 가지 옵션이 있습니다. 현재 숫자 또는 현재 숫자에 currentMax를 곱하는 것입니다.

Math.max(3, 3 * -2)

분명히 첫 번째 옵션이므로 currentMax는 이제 3입니다.
currentMin을 업데이트하려면 다음 두 가지 옵션도 있습니다.

Math.min(3, 3 * -2)

또 뻔하네요, -6. 현재 우리의 가치는 다음과 같습니다.

currentMax // 3
currentMin // -6

다음 번호로 넘어갑니다. currentMax에는 두 가지 옵션이 있습니다.

Math.max(-4, -4 * 3)

그 자체로는 -4여야 하지만 배열을 보면 그렇지 않다는 것을 알 수 있습니다. 두 개의 음수 값을 곱하면 양수 값이 나오므로 currentMax는 24(-2 * 3 * -4)가 되어야 합니다.

Note

If we were to multiply it with currentMin, we reach this value: -4 * -6 = 24.

Also, let's look at our currentMin options:

Math.min(-4, -4 * -6)

This has to be -4 again, but something feels off.

The catch is that when we have negative numbers consecutively, our sign alternates, which affects the maximum result we need. That's why we're keeping track of the minimum value in the first case: to keep track of the sign.

Since the issue is just alternating signs, we can simply swap the maximum and minimum values when we're looking at a negative number before updating those values:

if (nums[i] < 0) {
  [currentMax, currentMin] = [currentMin, currentMax];
}

Also, note that we're taking the product of each previous subarray as we go, essentially solving a smaller portion of the problem.

And that's it, our final solution looks like this:

function maxProduct(nums: number[]): number {
  let currentMax = nums[0];
  let currentMin = nums[0];
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
      [currentMax, currentMin] = [currentMin, currentMax];
    }

    currentMax = Math.max(nums[i], nums[i] * currentMax);
    currentMin = Math.min(nums[i], nums[i] * currentMin);

    result = Math.max(result, currentMax);
  }

  return result;
}

Time and space complexity

The time complexity for this solution is $O(n)$O(n) because we go through each number once doing a constant operation.

Note

Math.max() and Math.min() are constant operations here, since we're comparing two values only. However, if we were to find max or min of a whole array, it would be $O(n)$O(n) as the time complexity of the operation would increase proportionately to the size of the array.

The space complexity is $O(1)$O(1) since we don't need any additional storage.

---

The next problem on the list is called Word Break. Until then, happy coding.

위 내용은 LeetCode 명상: 최대 제품 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!