Find Maximum Non-decreasing Array Length - Practice Coding Problems

Find Maximum Non-decreasing Array Length - Problem

Array Binary Search Dynamic Programming Stack Queue Monotonic Stack Monotonic Queue Hard

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.

Input & Output

Example 1 — Basic Merging

$ Input: nums = [5,2,4,6,3,7]

› Output: 3

💡 Note: We can merge subarrays: [5] + [2,4] + [6,3,7] = [5,6,16]. This gives us a non-decreasing array of length 3.

Example 2 — Already Non-decreasing

$ Input: nums = [1,3,5,6]

› Output: 4

💡 Note: Array is already non-decreasing, so no merging needed. Keep all elements: [1,3,5,6]. Length is 4.

Example 3 — Single Element

$ Input: nums = [1]

› Output: 1

💡 Note: Single element is always non-decreasing. No operations needed. Length is 1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [5,2,4,6,3,7]

Merge Strategy

Group elements to maintain non-decreasing sums

Result

Maximum length non-decreasing array

Key Takeaway

🎯 Key Insight: Use monotonic stack to greedily merge subarrays when they would violate non-decreasing property

Asked in

G Google 15 a Amazon 12 f Meta 8 M Microsoft 6

The key insight is to use a monotonic stack to greedily merge subarrays when needed to maintain the non-decreasing property. The optimal stack-based approach processes elements left to right, merging with previous sums when the current sum would violate non-decreasing order. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possible Subarrays	O(2ⁿ × n)	O(n)	Generate all possible ways to partition array into subarrays and check if resulting sums form non-decreasing sequence
Monotonic Stack - Greedy Approach	O(n)	O(n)	Use monotonic stack to greedily merge subarrays while maintaining non-decreasing property
Dynamic Programming with Binary Search	O(n³ log n)	O(n)	Use DP to track maximum length ending at each position with binary search optimization

Brute Force - Try All Possible Subarrays — Algorithm Steps

Generate all possible partitions of the array
For each partition, compute subarray sums
Check if sums form non-decreasing sequence
Track maximum valid length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Partitions

Try all ways to split [5,2,4,6,3,7]

Compute Sums

Replace each subarray with its sum

Check Non-decreasing

Verify if sums form non-decreasing sequence

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int maxLength;

void generatePartitions(int* nums, int n, int start, int** currentPartition, int* partitionSizes, int partitionCount) {
    if (start == n) {
        // Compute sums for current partition
        long long* sums = malloc(partitionCount * sizeof(long long));
        for (int i = 0; i < partitionCount; i++) {
            sums[i] = 0;
            for (int j = 0; j < partitionSizes[i]; j++) {
                sums[i] += currentPartition[i][j];
            }
        }
        
        // Check if non-decreasing
        bool isNonDecreasing = true;
        for (int i = 1; i < partitionCount; i++) {
            if (sums[i] < sums[i-1]) {
                isNonDecreasing = false;
                break;
            }
        }
        
        if (isNonDecreasing && partitionCount > maxLength) {
            maxLength = partitionCount;
        }
        
        free(sums);
        return;
    }
    
    // Try all possible end positions for next subarray
    for (int end = start; end < n; end++) {
        int subarraySize = end - start + 1;
        currentPartition[partitionCount] = malloc(subarraySize * sizeof(int));
        partitionSizes[partitionCount] = subarraySize;
        
        for (int i = 0; i < subarraySize; i++) {
            currentPartition[partitionCount][i] = nums[start + i];
        }
        
        generatePartitions(nums, n, end + 1, currentPartition, partitionSizes, partitionCount + 1);
        
        free(currentPartition[partitionCount]);
    }
}

int solution(int* nums, int n) {
    maxLength = 1;
    int** currentPartition = malloc(n * sizeof(int*));
    int* partitionSizes = malloc(n * sizeof(int));
    
    generatePartitions(nums, n, 0, currentPartition, partitionSizes, 0);
    
    free(currentPartition);
    free(partitionSizes);
    return maxLength;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n possible partitions, each requiring O(n) time to compute and validate

✓ Linear Growth

Space Complexity

O(n)

Recursion stack and temporary arrays to store current partition

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possible Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler