2945. Find Maximum Non-decreasing Array Length LeetCode Solution
In this guide, you will get 2945. Find Maximum Non-decreasing Array Length LeetCode Solution with the best time and space complexity. The solution to Find Maximum Non-decreasing Array Length problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Maximum Non-decreasing Array Length
You are given a 0-indexed integer array nums.
You can perform any number of operations, where each operation involves selecting a subarray of the array and replacing it with the sum of its elements. For example, if the given array is [1,3,5,6] and you select subarray [3,5] the array will convert to [1,8,6].
Return the maximum length of a non-decreasing array that can be made after applying operations.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [5,2,2]
Output: 1
Explanation: This array with length 3 is not non-decreasing.
We have two ways to make the array length two.
First, choosing subarray [2,2] converts the array to [5,4].
Second, choosing subarray [5,2] converts the array to [7,2].
In these two ways the array is not non-decreasing.
And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing.
So the answer is 1.
Input: nums = [1,2,3,4]
Output: 4
Explanation: The array is non-decreasing. So the answer is 4.
Example 3:
Input: nums = [4,3,2,6]
Output: 3
Explanation: Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing.
Because the given array is not non-decreasing, the maximum possible answer is 3.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 105
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
2945. Find Maximum Non-decreasing Array Length LeetCode Solution in C++
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 /* code provided by PROGIEZ */
2945. Find Maximum Non-decreasing Array Length LeetCode Solution in Java
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] // code provided by PROGIEZ
2945. Find Maximum Non-decreasing Array Length LeetCode Solution in Python
