Finding the Maximum Length of a Non-Decreasing Array - Java - 10 ms beats 100% - 59 mb
Intuition\nThe problem involves maximizing the length of a non-decreasing subarray after performing operations that allow us to replace subarrays with their sum
# Intuition\nThe problem involves maximizing the length of a non-decreasing subarray after performing operations that allow us to replace subarrays with their sums. The key insight is that by calculating prefix sums, we can determine how subarrays can be combined and tracked to form a non-decreasing sequence.\n\n# Approach\n1. Prefix Sum Calculation: Start by computing the prefix sums for the array, which will help us efficiently calculate the sum of any subarray.\n2. Dynamic Programming and Queue Management: Use dynamic programming to track the maximum length of a non-decreasing subarray that can be formed up to each index. A queue is maintained to track the indices of subarrays that could potentially extend the sequence.\n    - For each element, adjust the queue to ensure that the current element can be added to the sequence while maintaining the non-decreasing property.\n    - If the sum of the current prefix and a previous subarray (tracked in the queue) forms a valid sequence, update the maximum length and continue.\n3. Monotonic Queue: The queue is maintained in a way that ensures it is monotonic, meaning it always contains the best candidates for extending the sequence without redundant elements.\n\n# Complexity\n- Time complexity:\n    - The algorithm runs in O(n), where n is the length of the input array. This is because each element is processed once and the queue operations are amortized to constant time.\n\n- Space complexity:\n    - O(n) due to the additional arrays used for storing prefix sums, maximum sums, and lengths.\n\n# Code\n```java []\npublic class Solution {\n    public int findMaximumLength(int[] nums) {\n        int n = nums.length;\n        int[] queue = new int[n + 1];  // Queue to track indices\n        int writeIndex = 0;  // Pointer for writing to the queue\n        int readIndex = 0;   // Pointer for reading from the queue\n        long[] prefixSum = new long[n + 1];  // Prefix sums of the array\n        long[] maxSums = new long[n + 1];  // Array to store the maximum sums\n        int[] maxLength = new int[n + 1];  // Array to store the maximum lengths\n\n        // Compute prefix sums\n        for (int i = 1; i <= n; i++) {\n            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];\n\n            // Update read index to maintain non-decreasing order\n            while (readIndex < writeIndex && prefixSum[i] >= maxSums[readIndex + 1]) {\n                readIndex++;\n            }\n\n            // Find the best previous index to extend the sequence\n            int bestIndex = queue[readIndex];\n            long subarraySum = prefixSum[i] - prefixSum[bestIndex];\n            maxLength[i] = maxLength[bestIndex] + 1;\n\n            // Calculate the new sum to compare with future elements\n            long newSum = prefixSum[i] + subarraySum;\n\n            // Maintain the monotonicity of maxSums by removing dominated elements\n            while (newSum <= maxSums[writeIndex]) {\n                writeIndex--;\n            }\n\n            // Update the queue and maxSums with the new index\n            queue[++writeIndex] = i;\n            maxSums[writeIndex] = newSum;\n        }\n\n        // Return the maximum length of a non-decreasing sequence\n        return maxLength[n];\n    }\n}\n```
['Array', 'Binary Search', 'Dynamic Programming', 'Stack', 'Queue', 'Monotonic Stack', 'Java']