✅☑[C++/Java/Python/JavaScript] || Easy Approach || EXPLAINED🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n(Also explained in the code)\n\n1. Prefix Sum Array:\n\n    - pre is a prefix sum array storing cumulative 
# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n**(Also explained in the code)**\n\n1. **Prefix Sum Array:**\n\n    - `pre` is a prefix sum array storing cumulative sums of the elements in `nums`.\n1. **Dynamic Programming Approach:**\n\n    - `dp[i]` represents the maximum length of a subarray ending at index `i` and its last element value.\n1. **Initialization:**\n\n    - `dp[0]` is initialized with `{0, 0}` as there\'s no subarray for index `0`.\n1. **Loop Through Elements:**\n\n    - The loop iterates through each element of the `nums` array.\n1. **Subarray Comparison:**\n\n    - Compares the current element with the last element of the previous subarray and updates dp[i] accordingly.\n1. **Finding Index with Binary Search:**\n\n    - Calculates `lbneed`, the value needed to achieve the sum with the current element.\n    - Uses binary search (`lower_bound`) to find the index `id` where the sum reaches `lbneed`.\n    - Updates `dp[id]` if a valid index is found.\n1. **Return:**\n\n    - Returns the maximum length of the subarray, stored in `dp[N]`.first.\n\n\n# Complexity\n- *Time complexity:*\n   $$O(nlogn)$$\n    \n\n- *Space complexity:*\n   $$O(n)$$\n    \n\n\n# Code\n```C++ []\n#define ll long long\n\nclass Solution {\npublic:\n    int findMaximumLength(vector<int>& nums) {\n        int N = nums.size();\n        \n        // Creating a prefix sum array to store cumulative sums of the elements in nums\n        vector<ll> pre;\n        pre.push_back(0); // Initializing with 0 as the first element\n        for(auto x : nums) \n            pre.push_back((ll)x); // Converting int to ll and storing cumulative sum\n        for(ll i = 1; i <= N; i++)\n            pre[i] += pre[i - 1]; // Calculating cumulative sum\n        \n        // Using a dynamic programming approach to solve the problem\n        // dp[i] stores the maximum length of a subarray ending at index i and its last element value\n        \n        // Initializing dp array with pair {0, 0}\n        vector<pair<ll, ll>> dp(N + 1, {0, 0});\n        dp[0] = {0, 0};\n\n        for(ll i = 1; i <= N; i++) {\n            auto [len, x] = dp[i - 1]; // Extracting length and last element value from previous state\n\n            x *= -1LL; // Multiplying by -1 for comparison purposes\n            \n            // Comparing current element with the last element of the previous subarray\n            if(x <= nums[i - 1]) {\n                dp[i] = max(dp[i], {len + 1, -1LL * nums[i - 1]});\n            } else {\n                dp[i] = max(dp[i], {len, -1LL * (x + (ll)nums[i - 1])});\n            }\n\n            // Finding the index where the sum would be equal to lbneed using binary search\n            ll lbneed = pre[i] - nums[i - 1] + x;\n            ll id = lower_bound(pre.begin(), pre.end(), lbneed) - pre.begin();\n            \n            // Updating dp[id] if valid index is found\n            if(id <= N)\n                dp[id] = max(dp[id], {len + 1, -1LL * (x + pre[id] - lbneed)});\n        }\n        \n        // Returning the maximum length of the subarray\n        return dp[N].first;\n    }\n};\n\n\n\n```\n```C []\n#define MAX_SIZE 10000\n\ntypedef long long ll;\n\nstruct Pair {\n    ll first;\n    ll second;\n};\n\nint findMaximumLength(int nums[], int numsSize) {\n    ll pre[MAX_SIZE + 1];\n    struct Pair dp[MAX_SIZE + 1];\n\n    pre[0] = 0;\n    for (int i = 0; i < numsSize; i++) {\n        pre[i + 1] = (ll)nums[i];\n    }\n    for (ll i = 1; i <= numsSize; i++) {\n        pre[i] += pre[i - 1];\n    }\n    dp[0].first = 0;\n    dp[0].second = 0;\n\n    for (ll i = 1; i <= numsSize; i++) {\n        ll len = dp[i - 1].first;\n        ll x = dp[i - 1].second;\n        x *= -1LL;\n        if (x <= nums[i - 1]) {\n            if (dp[i].first < len + 1) {\n                dp[i].first = len + 1;\n                dp[i].second = -1LL * nums[i - 1];\n            }\n        } else {\n            if (dp[i].first < len) {\n                dp[i].first = len;\n                dp[i].second = -1LL * (x + (ll)nums[i - 1]);\n            }\n        }\n        ll lbneed = pre[i] - nums[i - 1] + x;\n        ll id = 0;\n        for (int j = 0; j <= numsSize; j++) {\n            if (pre[j] < lbneed) {\n                id = j;\n            } else {\n                break;\n            }\n        }\n        if (id <= numsSize) {\n            if (dp[id].first < len + 1) {\n                dp[id].first = len + 1;\n                dp[id].second = -1LL * (x + pre[id] - lbneed);\n            }\n        }\n    }\n    return dp[numsSize].first;\n}\n\n\n\n```\n```Java []\n\n\nclass Solution {\n    public int findMaximumLength(int[] nums) {\n        int N = nums.length;\n        List<Long> pre = new ArrayList<>();\n        pre.add(0L);\n        for (int x : nums) pre.add((long) x);\n        for (int i = 1; i <= N; i++)\n            pre.set(i, pre.get(i) + pre.get(i - 1));\n\n        List<Pair<Long, Long>> dp = new ArrayList<>(Collections.nCopies(N + 1, new Pair<>(0L, 0L)));\n        dp.set(0, new Pair<>(0L, 0L));\n\n        for (long i = 1; i <= N; i++) {\n            Pair<Long, Long> pair = dp.get((int) (i - 1));\n            long len = pair.getKey();\n            long x = pair.getValue();\n            x *= -1L;\n\n            if (x <= nums[(int) (i - 1)]) {\n                dp.set((int) i, max(dp.get((int) i), new Pair<>(len + 1, -1L * nums[(int) (i - 1)])));\n            } else {\n                dp.set((int) i, max(dp.get((int) i), new Pair<>(len, -1L * (x + (long) nums[(int) (i - 1)]))));\n            }\n\n            long lbneed = pre.get((int) i) - nums[(int) (i - 1)] + x;\n            int id = Collections.binarySearch(pre, lbneed);\n            if (id >= 0) id++;\n            else id = -id - 1;\n            if (id <= N)\n                dp.set(id, max(dp.get(id), new Pair<>(len + 1, -1L * (x + pre.get(id) - lbneed))));\n        }\n        return dp.get(N).getKey().intValue();\n    }\n\n    private Pair<Long, Long> max(Pair<Long, Long> a, Pair<Long, Long> b) {\n        return a.getKey() > b.getKey() ? a : b;\n    }\n}\n\n\n\n```\n```python3 []\n\n\nclass Solution:\n    def findMaximumLength(self, nums):\n        N = len(nums)\n        pre = [0]\n        pre.extend(nums)\n        for i in range(1, N + 1):\n            pre[i] += pre[i - 1]\n\n        dp = defaultdict(lambda: (0, 0))\n        dp[0] = (0, 0)\n\n        for i in range(1, N + 1):\n            length, x = dp[i - 1]\n            x *= -1\n\n            if x <= nums[i - 1]:\n                dp[i] = max(dp[i], (length + 1, -1 * nums[i - 1]))\n            else:\n                dp[i] = max(dp[i], (length, -1 * (x + nums[i - 1])))\n\n            lb_need = pre[i] - nums[i - 1] + x\n            id = next((idx for idx, val in enumerate(pre) if val >= lb_need), N + 1)\n            if id <= N:\n                dp[id] = max(dp[id], (length + 1, -1 * (x + pre[id] - lb_need)))\n\n        return dp[N][0]\n\n\n\n```\n```javascript []\nfunction findMaximumLength(nums) {\n    const N = nums.length;\n    const pre = [0];\n    for (const x of nums) {\n        pre.push(BigInt(x));\n    }\n    for (let i = 1; i <= N; i++) {\n        pre[i] += pre[i - 1];\n    }\n    const dp = Array(N + 1).fill({ first: 0, second: 0 });\n    dp[0] = { first: 0, second: 0 };\n\n    for (let i = 1; i <= N; i++) {\n        const [len, x] = [dp[i - 1].first, dp[i - 1].second];\n        let newX = -1n * x;\n        if (newX <= BigInt(nums[i - 1])) {\n            dp[i] = { first: Math.max(dp[i].first, len + 1), second: -1n * BigInt(nums[i - 1]) };\n        } else {\n            dp[i] = { first: Math.max(dp[i].first, len), second: -1n * (newX + BigInt(nums[i - 1])) };\n        }\n        const lbneed = pre[i] - BigInt(nums[i - 1]) + newX;\n        const id = pre.findIndex((val) => val >= lbneed);\n        if (id !== -1 && id <= N) {\n            dp[id] = { first: Math.max(dp[id].first, len + 1), second: -1n * (newX + pre[id] - lbneed) };\n        }\n    }\n    return dp[N].first;\n}\n\n\n\n\n```\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---
['Array', 'Dynamic Programming', 'C', 'Prefix Sum', 'C++', 'Java', 'Python3', 'JavaScript']