# Maximum Sub Array

Hi Geeks! Welcome to 100 Days of Leetcode Challenge.

Day 29

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.
```

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

## Approach

### Using DP

```public class Solution {
public int MaxSubArray(int[] nums) {
int[] dp = new int[nums.Length];
dp = nums;
int max = nums;
for(int i=1;i<nums.Length;i++)
{
if(dp[i-1] <= 0)
dp[i] = nums[i];
else if(dp[i-1] > 0){
if(nums[i] + dp[i-1] <= 0)
dp[i] = nums[i];
else
dp[i] = nums[i] + dp[i-1];
}
max = Math.Max(dp[i],max);
}
return max;
}
}```

It takes, O(n) time complexity and O(n) Space Complexity.

How can we reduce space complexity to O(1)? Can we able to solve that?

Yes, we can, by introducing two variables.

```public class Solution {
public int MaxSubArray(int[] nums) {

int prev = nums;
int current = 0;
int max = nums;
for(int i=1;i<nums.Length;i++)
{
if(prev <= 0)
current = nums[i];
else{
if(nums[i] + prev <= 0)
current = nums[i];
else
current = nums[i] + prev;
}
max = Math.Max(current,max);
prev = current;
}
return max;
}
}```