| 22 | } |
| 23 | |
| 24 | private int helper(int[] nums, int left, int right) { |
| 25 | if (left >= right) return nums[left]; |
| 26 | int mid = (left + right) >> 1; |
| 27 | int leftAns = helper(nums, left, mid); |
| 28 | int rightAns = helper(nums, mid + 1, right); |
| 29 | int leftMax = nums[mid], rightMax = nums[mid + 1]; |
| 30 | int temp = 0; |
| 31 | for (int i = mid; i >= left; --i) { |
| 32 | temp += nums[i]; |
| 33 | if (temp > leftMax) leftMax = temp; |
| 34 | } |
| 35 | temp = 0; |
| 36 | for (int i = mid + 1; i <= right; ++i) { |
| 37 | temp += nums[i]; |
| 38 | if (temp > rightMax) rightMax = temp; |
| 39 | } |
| 40 | return Math.max(Math.max(leftAns, rightAns), leftMax + rightMax); |
| 41 | } |
| 42 | |
| 43 | public static void main(String[] args) { |
| 44 | Solution solution = new Solution(); |