# Maximum Subarray Sum

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

Please check the following Algorithm for a better understanding :

`int [] arr  =  {2, -9, 5, 1, -4, 6, 0, -7, 8};`

In this case, the output sub-array Starts from the value 5 (`index position: arr[2]`) and ends with value 8 (`index position: arr[8]`). Check the following step by step calculation. The following figure is describing the desired subarray only.

#### Approach 1: Greedy

Intuition

The problem to find maximum (or minimum) element (or sum) with a single array as the input is a good candidate to be solved by the greedy approach in linear time.

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

The algorithm is general and straightforward: iterate over the array and update at each step the standard set for such problems:

• current element
• current `local maximum` sum (at this given point)
• The`global maximum sum` is seen so far.

If all are negative numbers then keep track of the minimum negative number. Because that will be our max subarray sum. Following is the `Java` implementation.

```class Solution {

public static void main(String[] args) {
int[] arr = {0, -1};
System.out.println(maxSubArray(arr));
}

public static int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int curSum = 0;
int maxSum = 0;
boolean isAllNegative = true;
int minNegative = Integer.MIN_VALUE;

for (int i = 0; i < nums.length; i++) {

// We found a positive number or a zero in the array
if (nums[i] >= 0 && isAllNegative) {
isAllNegative = false;
}

/**
* Track the minimum negative number in the array
* when all array numbers are negative
*/
if (nums[i] < 0 && nums[i] > minNegative && isAllNegative) {
minNegative = nums[i];
}

// Adding array elements one by one
curSum += nums[i];

// Replace currentSum with 0 when it becomes less than 0
if (curSum < 0) {
curSum = 0;
}
// Replace the maximum sum when the current sum is greater.
// Means we have a new sub-array with greater sum
if (maxSum < curSum) {
maxSum = curSum;
}
}
return isAllNegative ? minNegative : maxSum;
}
}
```

Complexity Analysis:

• Time complexity: `O(N)` since it’s one pass along the array.
• Space complexity: `O(1)`, since it’s a constant space solution.

#### Approach 2: Dynamic Programming (Kadane’s Algorithm)

The problem to find a sum or maximum or the minimum in an entire array or in a fixed-size sliding window could be solved by the `Dynamic Programming (DP)` approach in linear time.

There are two standard DP approaches suitable for arrays:

• Constant space one. Move along the array and modify the array itself.
• Linear space one. The first move in the direction `left->right`, then in the direction `right->left`. Combine the results.

Let’s use here the first approach since one could modify the array to track the current local maximum sum at this given point.

The next step is to update the `global maximum sum`, knowing the `local one`.

```class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length, maxSum = nums[0];
for(int i = 1; i < n; ++i) {
if (nums[i - 1] > 0) nums[i] += nums[i - 1];
maxSum = Math.max(nums[i], maxSum);
}
return maxSum;
}
}
```

Complexity Analysis

• Time complexity: `O(N)` since it’s one pass along the array.
• Space complexity: `O(1)`, since it’s a constant space solution.

Categories: Dynamic Programming