✅Fully explained easy to understand solution🔥Java🔥Find Maximum Non-decreasing Array Length(2945)
Approach\n1. Cumulative Sums:\n- The code starts by calculating the cumulative sums of the input array nums and stores them in the array acc. This is done to ef
# Approach\n**1. Cumulative Sums:**\n- The code starts by calculating the cumulative sums of the input array nums and stores them in the array acc. This is done to efficiently compute the sum of any subarray later.\n```\nfor (int i = 1; i <= n; i++) {\n    acc[i] = acc[i - 1] + nums[i - 1];\n}\n```\n\n**2. **Dynamic Programming Loop:****\n\n- The main logic is inside a loop that iterates through the elements of the input array.\n- It maintains two arrays, dp and pre, for dynamic programming and index optimization, respectively.\n```\nfor (int i = 0, j = 1; j <= n; j++) {\n    // Optimize the starting index i if it was previously optimized\n    i = Math.max(i, pre[j]);\n\n    // Update the current dynamic programming result\n    dp[j] = dp[i] + 1;\n\n    // Binary search to find an index k where acc[k] is equal to 2 * acc[j] - acc[i]\n    int k = Arrays.binarySearch(acc, 2 * acc[j] - acc[i]);\n\n    // If the value is not found, get the insertion point to update the pre array\n    if (k < 0) {\n        k = -k - 1;\n    }\n\n    // Update the pre array with the current index j\n    pre[k] = j;\n}\n```\n\n- The key idea is to maintain an index i and use it to optimize the starting index of the current subarray. The dynamic programming array dp keeps track of the maximum length of subarrays ending at the current index j.\n- The binary search is used to find the index k such that acc[k] is equal to 2 * acc[j] - acc[i]. This is done to efficiently find the starting index i of a potential subarray with a sum equal to twice the sum of the current subarray.\n- The pre array is updated to store the current index j for future optimization.\n\n**3. Result:**\n\n- The result is obtained by returning dp[n], where n is the length of the input array. This represents the maximum length of a subarray with specific properties.\n---\n\n\n# Complexity\n- Time complexity:\nThe cumulative sums are calculated in O(n) time.\nThe dynamic programming loop has a binary search operation, which takes O(log n) time for each iteration.\nOverall, the time complexity is O(n * log n), where n is the length of the input array.\n\n- Space complexity:\nThe space complexity is O(n) because additional arrays pre, dp, and acc are used, each with a size proportional to the length of the input array.\n\n# Code\n```\npublic class Solution {\n    public int findMaximumLength(int[] nums) {\n        // Length of the input array\n        int n = nums.length;\n\n        // Arrays to store cumulative sums, dynamic programming results, and indices for optimization\n        int[] pre = new int[n + 2];\n        int[] dp = new int[n + 1];\n\n        // Array to store cumulative sums of the input array\n        long[] acc = new long[n + 1];\n\n        // Calculate cumulative sums\n        for (int i = 1; i <= n; i++) {\n            acc[i] = acc[i - 1] + nums[i - 1];\n        }\n\n        // Iterate through the elements of the input array\n        for (int i = 0, j = 1; j <= n; j++) {\n            // Optimize the starting index i if it was previously optimized\n            i = Math.max(i, pre[j]);\n\n            // Update the current dynamic programming result\n            dp[j] = dp[i] + 1;\n\n            // Binary search to find an index k where acc[k] is equal to 2 * acc[j] - acc[i]\n            int k = Arrays.binarySearch(acc, 2 * acc[j] - acc[i]);\n\n            // If the value is not found, get the insertion point to update the pre array\n            if (k < 0) {\n                k = -k - 1;\n            }\n\n            // Update the pre array with the current index j\n            pre[k] = j;\n        }\n\n        // Return the maximum length of the subarray\n        return dp[n];\n    }\n}\n\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/3b9fa641-fa0c-4176-9910-3c60521bdc74_1702364363.4617372.png)\n
['Java']