Find maximum non decreasing array length

Array Binary Search Dynamic Programming Stack Queue Monotonic Stack Monotonic Queue

18.5% acceptance

Feb 25, 2026

214

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximum_length(nums: Vec<i32>) -> i32 {
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;

    let n = nums.len();
    // prefix[i] = sum of nums[0..i]
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + nums[i] as i64;
    }

    // dp[i] = max non-decreasing partition length for nums[0..i] (covering indices 0..i-1)
    // g(j) = f(j) + prefix[j+1] where f(j) = last group sum in dp[j] partition
    // dp[i] = 1 + max k s.t. valid_px[k] > 0 and the entry became valid
    // Key: g(j) > prefix[j+1], so entries become valid later

    // Heap min by g value; entries: (g, dp_val, prefix_j_plus1)
    let mut heap: BinaryHeap<Reverse<(i64, i32, i64)>> = BinaryHeap::new();
    // virtual base: dp=0, g=0, px=prefix[0]=0
    heap.push(Reverse((0i64, 0i32, 0i64)));

    let mut valid_px: Vec<i64> = vec![-1; n + 2];
    valid_px[0] = 0;
    let mut max_k: i32 = 0;

    let mut last_dp = 0i32;
    for i in 0..n {
      let t = prefix[i + 1];
      // Activate entries with g <= t
      while let Some(&Reverse((g, dv, px))) = heap.peek() {
        if g <= t {
          heap.pop();
          if valid_px[dv as usize] < px {
            valid_px[dv as usize] = px;
          }
          if dv > max_k {
            max_k = dv;
          }
        } else {
          break;
        }
      }
      let dp_i = max_k + 1;
      last_dp = dp_i;
      let best_px = valid_px[max_k as usize]; // guaranteed >= 0
      let g_i = 2 * t - best_px;
      heap.push(Reverse((g_i, dp_i, t)));
    }

    last_dp
  }
}