# Maximum Subarray

{% hint style="info" %}
Array, Dynamic Programming
{% endhint %}

Given an integer array `nums`, find the subarray with the largest *sum*, and return its *sum*. Here, array can contains duplicate or nagative numbers also.

Example 1:

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

Example 2:

```
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
```

Example 3:

```
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
```

### Solutions

Calculates the maximum sum ending at each position and ensures that this sum is the maximum seen so far.

#### **Approach – Brute Force Technique**

This algorithm works by calculating the sum of every possible subarray in the input array and updating `maxSum` whenever a larger sum is found.

**Steps**

1. **Initialize**: Set `maxSum` to the smallest possible integer. This variable will keep track of the maximum subarray sum we've encountered so far.
2. **Iterate through the array**: For each element in the array (index `i` from 0 to `nums.Length - 1`), calculate the sum of all subarrays starting at this position. This is done by another loop (index `j` from `i` to `nums.Length - 1`) that adds the current element (`nums[j]`) to `sum`.
3. **Update `maxSum`**: If `sum` is greater than `maxSum`, update `maxSum` with the value of `sum`. This step keeps track of the maximum sum of any subarray seen so far.
4. **Return the result**: After going through all the elements of the array and all possible subarrays, return `maxSum` which now contains the maximum sum of a subarray in the array.

```csharp
public class Solution {
    public int MaxSubArray(int[] nums) {
        int maxSum = Int32.MinValue;
        for (int i = 0; i < nums.Length; i++) {
            int sum = 0;
            for (int j = i; j < nums.Length; j++) {
                sum += nums[j];
                maxSum = Math.Max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

```

> Complexity

* **Time Complexity:** O(n^2)
* **Auxiliary Space:** O(1)

#### **Approach – Dynamic Programming Technique**

It calculates the maximum sum ending at each position and ensures that this sum is the maximum seen so far. If the sum becomes less than the current element, it means the sum of the previous subarray is negative and thus not worth keeping, so it starts a new subarray from the current position.

**Steps**

1. **Initialize**: Set `maxCurrent` and `maxGlobal` to the first element of the array. These variables will keep track of the maximum subarray sum we've encountered so far (`maxGlobal`) and the maximum sum ending at the current position (`maxCurrent`).
2. **Iterate through the array**: For each element from the second to the last (index `i` from 1 to `nums.Length - 1`), update `maxCurrent` to be the maximum of the current element (`nums[i]`) and the sum of the current element and the previous `maxCurrent` (`maxCurrent + nums[i]`). This step essentially says, "consider the current element as the start of a new subarray or include it in the sum of the existing subarray."
3. **Update `maxGlobal`**: If `maxCurrent` is greater than `maxGlobal`, update `maxGlobal` with the value of `maxCurrent`. This step keeps track of the maximum sum of any subarray seen so far.
4. **Return the result**: After going through all the elements of the array, return `maxGlobal` which now contains the maximum sum of a subarray in the array.

```csharp
public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        int maxCurrent = nums[0];
        int maxGlobal = nums[0];

        for (int i = 1; i < nums.Length; i++)
        {
            maxCurrent = Math.Max(nums[i], maxCurrent + nums[i]);
            if (maxCurrent > maxGlobal)
            {
                maxGlobal = maxCurrent;
            }
        }
        return maxGlobal;
    }
}

```

> Complexity

* **Time Complexity:** O(n)
* **Auxiliary Space:** O(1)