find-maximum-non-decreasing-array-length

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a 0-indexed integer array <code>nums</code>.

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 <code>[1,3,5,6]</code> and you select subarray <code>[3,5]</code> the array will convert to <code>[1,8,6]</code>.

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.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
Input: nums = [1,2,3,4]
Output: 4
Explanation: The array is non-decreasing. So the answer is 4.
</pre>

Example 3:

<pre>
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.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

findMaximumLength

Find Maximum Non-decreasing Array Length

Stack

Queue

Array

Binary Search

Dynamic Programming

Monotonic Queue

Monotonic Stack

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。

你可以执行任意次操作。每次操作中，你需要选择一个 子数组&nbsp;，并将这个子数组用它所包含元素的 和&nbsp;替换。比方说，给定数组是&nbsp;<code>[1,3,5,6]</code>&nbsp;，你可以选择子数组&nbsp;<code>[3,5]</code>&nbsp;，用子数组的和 <code>8</code>&nbsp;替换掉子数组，然后数组会变为&nbsp;<code>[1,8,6]</code>&nbsp;。

请你返回执行任意次操作以后，可以得到的 最长非递减&nbsp;数组的长度。

子数组&nbsp;指的是一个数组中一段连续 非空&nbsp;的元素序列。

&nbsp;

示例 1：

<pre>
输入：nums = [5,2,2]
输出：1
解释：这个长度为 3 的数组不是非递减的。
我们有 2 种方案使数组长度为 2 。
第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。
第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。
这两种方案中，数组最后都不是 非递减&nbsp;的，所以不是可行的答案。
如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。
所以答案为 1 。
</pre>

示例 2：

<pre>
输入：nums = [1,2,3,4]
输出：4
解释：数组已经是非递减的。所以答案为 4 。
</pre>

示例 3：

<pre>
输入：nums = [4,3,2,6]
输出：3
解释：将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。
最大可能的答案为 3 。</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>