We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Maximum Non-decreasing Array Length

Number: 3211

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given an integer array nums, you may perform any number of operations. In each operation you choose a contiguous subarray and replace it with the sum of its elements. Your goal is to achieve a non-decreasing array (i.e. each element is no smaller than its previous one) while keeping the length as long as possible. Return the maximum possible length of a non-decreasing array that can be obtained after applying these operations.

For example, for nums = [4,3,2,6], one optimal move is to merge the subarray [3,2] into 5, resulting in the array [4,5,6] which is non-decreasing. However, if no proper segmentation exists (as in [5,2,2] where any two‐segment partition is invalid), you may need to merge the entire array into a single number.

Key Insights

  • The operations allow merging contiguous segments, meaning you can group adjacent elements.
  • The final non-decreasing array can be seen as a partitioning of the original array into segments whose sums are non-decreasing.
  • To maximize the length (number of segments), you want as many segments as possible – i.e. you wish to partition the array into the maximum number of contiguous segments satisfying seg1 ≤ seg2 ≤ … ≤ segk.
  • A greedy strategy works: build segments from left to right, always ending a segment as soon as its sum is at least the sum of the previous segment.
  • This is optimal because delaying the partition would only increase the sum of the current segment (making it harder for the next segment to satisfy the ordering condition) and therefore may force you to merge more later.

Space and Time Complexity

Time Complexity: O(n) – We scan the array once. Space Complexity: O(1) – Only a few variables are used.

Solution

We interpret the problem as partitioning the array into contiguous segments. Let each segment’s value be the sum of the numbers in that segment. We wish for these segment sums to form a non-decreasing sequence, and we want to maximize the number of segments (i.e. the length of the resulting array).

We can solve this greedily as follows:

  1. Initialize prev_segment_sum as 0 (since every segment sum is positive, starting with 0 is safe).
  2. Iterate through the array while accumulating a running sum (current_segment_sum).
  3. As soon as the running sum is greater than or equal to the previous segment’s sum, cut the segment – this ensures the new segment is as small as possible and will provide a lower threshold for the next segment.
  4. Update prev_segment_sum with the current segment's sum and reset the running sum.
  5. Continue until the end of the array. The total number of segments created is the answer.

This approach works because having smaller segment sums early on relaxes the requirement for later segments. Delaying the cut (i.e. merging more than needed) unnecessarily increases the current segment sum and might force a larger next segment or even force you to merge a larger number of elements later—in the worst case, reducing the final length.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def maxNonDecreasingLength(self, nums: List[int]) -> int:
        # Initialize the count of segments and the sum of the previous segment.
        segment_count = 0
        prev_segment_sum = 0
        # Running sum for the current potential segment.
        current_segment_sum = 0
        
        # Iterate over each number in the array.
        for num in nums:
            # Add the current number to the current segment sum.
            current_segment_sum += num
            # Check if current segment sum is at least as large as the previous segment's sum.
            if current_segment_sum >= prev_segment_sum:
                # If yes, we can form a valid segment.
                segment_count += 1
                # Update previous segment sum for the next segment.
                prev_segment_sum = current_segment_sum
                # Reset current segment sum for the next segment.
                current_segment_sum = 0
        
        # Return the maximum number of segments obtained.
        return segment_count

# Example usage:
# sol = Solution()
# print(sol.maxNonDecreasingLength([4,3,2,6]))  # Output: 3
← Back to All Questions