53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 1 class Solution {
 2     public int maxSubArray(int[] nums) {
 3         int n = nums.length;
 4         int now = nums[0];
 5         int ans = nums[0];
 6         for (int i = 1; i < n; ++i) {
 7             
 8             if (now + nums[i] < nums[i]) {
 9                 
10                 now = nums[i];
11             } else {
12                 now = now + nums[i];
13             }
14             
15             ans = Math.max(ans, now);
16             
17         }
18         return ans;
19     }
20 }