java prefixSum binarySearch
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  public int findMaximumLength(int[] nums) {\n\n       // 1. \uC804\uCCB4 \uD655\uC778\uC758 \uACBD\uC6B0\uB294 i:0~n-1 \uAE4C\uC9C0 \uC21C\uD68C\uD558\uBA74\uC11C \n        //   1) preSum\uC744 \uAD6C\uD574 \uB193\uB294\uB2E4. \n        //   2) sum\uC744 \uACC4\uC18D \uB204\uC801\uC2DC\uD0A8\uB2E4.\n        //   3) lastNum[] \uBC30\uC5F4\uC73C \uB9CC\uB4E4\uC5B4\uC11C dp[i]\uC758 \uAC12\uC774 \uAC00\uC7A5 \uD074 \uB54C\uC758 sum-preSum[i]\uAC12\uC744 lastNum[i]\uC5D0 \uC800\uC7A5\uD55C\uB2E4.\n        //   4) j:i-1~0 \uAE4C\uC9C0 \uC21C\uD68C\uD558\uBA74\uC11C \n        //     \uC804\uCCB4 \uB204\uC801 \uAC12 - j\uAE4C\uC9C0\uC758 preSum \uC774 j\uC758 lastNum\uBCF4\uB2E4 \uD06C\uBA74 Non-decreasing Array\uAC00 \uB418\uAE30 \uB54C\uBB38\uC5D0 \n        //     sum - preSum[j] >= lastNum[j] \uC774 \uC870\uAC74\uC774 \uB9CC\uC871\uD558\uBA74 \n        //    dp[i] = Math.max(dp[i], dp[j]+1) \uB85C \uAC31\uC2E0\uD55C\uB2E4. \n        //    \uAC31\uC2E0\uC774 \uB418\uB294 \uACBD\uC6B0 lastNum[i] = sum-preSum[j] \uB3C4 \uC9C4\uD589\uD574\uC8FC\uACE0 \uC911\uC9C0\uD55C\uB2E4.(\uC55E\uC73C\uB85C \uAC08 \uC218\uB85D dp[j]\uAC00 \uC791\uC544\uC9C0\uBBC0\uB85C \uCC3E\uB294 \uC989\uC2DC \uC911\uC9C0)\n        //    \uD574\uB2F9 \uBC29\uBC95\uC73C\uB85C \uC9C4\uD589\uD558\uB294\uB294 \uACBD\uC6B0 O(n*n)\uC774 \uB418\uC5B4\uBC84\uB9B0\uB2E4. \n\n        // 2. binarySearch \uC774\uC6A9 \n        //   \u203B \uAC31\uC2E0\uC774 \uB418\uB294 \uACBD\uC6B0 lastNum[i] = sum-preSum[j] \uB3C4 \uC9C4\uD589\uD574\uC8FC\uACE0 \uC911\uC9C0\uD55C\uB2E4.(\uC55E\uC73C\uB85C \uAC08 \uC218\uB85D dp[j]\uAC00 \uC791\uC544\uC9C0\uBBC0\uB85C \uCC3E\uB294 \uC989\uC2DC \uC911\uC9C0)\n        //     \uC704 \uC870\uAC74\uC774 \uCDA9\uC871\uB418\uAE30 \uB54C\uBB38\uC5D0 \n        //     sum - preSum[j] >= lastNum[j] \uC2DD\uC744 \uBCC0\uD658\uD558\uBA74\n        //     sum >= lastNum[j] + preSum[j] \uC774\uC640 \uAC19\uC774 \uB418\uACE0 \n        //     lastNum[j] + preSum[j] \uAE30\uC900\uC73C\uB85C \uC815\uB82C\uB41C list\uC5D0\uC11C binarySearch\uB85C sum \uBCF4\uB2E4 \uC791\uAC70\uB098 \uAC19\uC740 \uAC12\uC744 o(logN) \uC2DC\uAC04\uC5D0 \uCC3E\uC744 \uC218 \uC788\uB2E4.\n        //     dp[i] \uAC00 \uACB0\uC815 \uB420 \uB54C\uB9C8\uB2E4  List<long[]> list \uC5D0 int[]{lastNum[j] + preSum[j], indexj} \uB97C \uCD94\uAC00\uD574\uC900\uB2E4.\n\n\n        int dp[] = new int[nums.length];\n        dp[0] = 1;\n\n        long preSum[] = new long[nums.length];\n        \n        preSum[0] = nums[0];\n        for(int i = 1; i < preSum.length; i++) {\n            preSum[i] = preSum[i-1]+nums[i];\n        }\n        \n        long sum = nums[0];\n        long lastNum[] = new long[nums.length];\n        lastNum[0] = nums[0];\n        List<long[]> list = new ArrayList<long[]>();\n        list.add(new long[]{preSum[0]+lastNum[0], 0});\n        \n        for(int i = 1; i < dp.length; i++) {\n            dp[i] = 1;\n            sum += nums[i];\n            // for(int j = i-1; j >= 0; j--) {\n            //     // System.out.println(sum - preSum[j] + " " + lastNum[j]);\n            //     if ( sum - preSum[j] >= lastNum[j]) {\n            //         if ( dp[i] < dp[j]+1) {\n            //             lastNum[i] = sum-preSum[j];\n            //             dp[i] = dp[j]+1;\n            //         }\n            //         break;\n            //     }\n            // }\n            // if ( dp[i] == 1 ) {\n            //     lastNum[i] = preSum[i];\n            // }\n\n            int idx = binarySearchUpper(list, sum);\n            // System.out.println(i + " " + idx + " " + sum);\n            idx--;\n\n            if ( idx >= 0 && list.get(idx)[0] <= sum ) {\n                int findIdx = (int)list.get(idx)[1];\n                if ( dp[i] < dp[findIdx]+1) {\n                    lastNum[i] = sum - preSum[findIdx];\n                    dp[i] = dp[findIdx]+1;\n                } else{\n                    lastNum[i] = preSum[i];\n                }\n            } else{\n                lastNum[i] = preSum[i];\n            }\n\n            idx = binarySearchUpper(list, preSum[i]+lastNum[i]);\n            while(idx < list.size()) list.remove(idx);\n            list.add(idx, new long[]{preSum[i]+lastNum[i], i});\n\n            // for(int a = 0; a < list.size(); a++) System.out.print("[" +list.get(a)[0] + " " + list.get(a)[1] + "]"); System.out.println();\n            \n        }\n\n        // for(int i = 0; i < dp.length; i++) System.out.print(dp[i] + " "); System.out.println();\n        // for(int i = 0; i < dp.length; i++) System.out.print(lastNum[i] + " "); System.out.println();\n        \n        return dp[dp.length-1];\n    }\n    private int binarySearchUpper(List<long[]> list , long sum) {\n        int start = 0;\n        int end = list.size(); \n        int mid;\n\n        while(start < end) {\n            mid = (start + end)/2;\n\n            if (  list.get(mid)[0] > sum) {\n                end = mid;\n            } else{\n                start = mid+1;\n            }\n        }\n\n        return end;\n    }\n}\n```
['Binary Search', 'Prefix Sum', 'Java']