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;
}
```