# Share my java solution

• First, tried Brute Force, which takes O(n^2). of course, it failed due to time limit exceeding.

Second, tried Dynamic Programing, which takes O(n) time O(1) space.

There are 2 cases, ith element is taken to Max(curr) or Not(nocurr).

finally, return max between curr and nocurr.

``````public int maxSubArray(int[] nums) {

if(nums==null || nums.length<1)
return 0;

int curr   = nums[0]; // ith is included
Integer nocurr = null;       // ith is not included

for(int i=1;i<nums.length;i++){
//ith is not included in max
nocurr = nocurr==null? curr:Math.max(curr,nocurr);

//ith is included in max
curr = Math.max(curr+nums[i], nums[i]);
}

return nocurr==null?curr:Math.max(nocurr, curr);

// O(n^2)  - time limit exceeded
// int[][] sum = new int[nums.length][nums.length];
// Integer maxsum = nums[0];

// for(int i=0;i<nums.length;i++){
//     sum[i][i] = nums[i];
//     for(int j=i+1;j<nums.length;j++){
//         sum[i][j] = sum[i][j-1]=nums[j];
//         maxsum = Math.max(maxsum,sum[i][j]);
//     }
// }
// return (int)maxsum;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.