Skip to content

2945. Find Maximum Non-decreasing Array Length 👍

Approach 1: TLE

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  def findMaximumLength(self, nums: list[int]) -> int:
    n = len(nums)
    kInf = 10_000_000_000
    # prefix[i] := the sum of the first i nums
    prefix = list(itertools.accumulate(nums, initial=0))
    # dp[i] := the maximum number of elements in the increasing
    # sequence after processing the first i nums
    dp = [0] * (n + 1)
    # last[i] := the last sum after processing the first i nums
    last = [0] + [kInf] * n

    for i in range(n):
      j = self._findIndex(i, prefix, last)
      dp[i + 1] = max(dp[i], dp[j] + 1)
      last[i + 1] = prefix[i + 1] - prefix[j]

    return dp[n]

  def _findIndex(self, i: int, prefix: list[int], last: list[int]) -> int:
    """Returns the index in [0..i].

    Returns the maximum index j in [0..i] s.t.
    prefix[i + 1] - prefix[j] >= last[j].
    """
    for j in range(i, -1, -1):
      if prefix[i + 1] - prefix[j] >= last[j]:
        return j
  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def findMaximumLength(self, nums: list[int]) -> int:
    n = len(nums)
    # prefix[i] := the sum of the first i nums
    prefix = list(itertools.accumulate(nums, initial=0))
    # dp[i] := the maximum number of elements in the increasing
    # sequence after processing the first i nums
    dp = [0] * (n + 1)
    # bestLeft[i] := the index l s.t. merging nums[l..i) is the
    # optimal strategy among processing the first i nums
    bestLeft = [0] * (n + 2)

    for i in range(1, n + 1):
      bestLeft[i] = max(bestLeft[i], bestLeft[i - 1])
      # When merging nums[l, i), consider the next segment as [i, r).
      # Find the minimum `r` where sum(nums[l, i)) <= sum(nums[i, r)).
      # Equivalently, prefix[i] - prefix[l] <= prefix[r] - prefix[i].
      #            => prefix[r] >= prefix[i] * 2 - prefix[l]
      # Therefore, we can binary search `prefix` to find the minimum `r`.
      l = bestLeft[i]
      r = bisect.bisect_left(prefix, 2 * prefix[i] - prefix[l])
      dp[i] = dp[l] + 1
      bestLeft[r] = i

    return dp[n]