Given an array A of N integers, the task is to find the contiguous sub-array(containing at least one number) which has the maximum sum and return the sub-array and its sum.

##### Example 1: Find largest sum contiguous sub-array in: {-2, -3, 4, -1, -2, 1, 5, -3}

**Input:** {-2, -3, 4, -1, -2, 1, 5, -3}

**Output:**Sub-array: { 4 -1 -2 1 5 }, Sum: 7

##### Example 2: Find largest sum contiguous sub-array in: {1}

**Input:** {1}

**Output:**Sub-array: { 1 }, Sum: 1

## Solutions

### Method 1: Kadane's Algorithm (Print Sub-array)

We can solve this problem with Kadane's Algorithm, the algorithm requires **at least one positive number**, so all negative array is invalid input.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.

### Method 2: Kadane's Algorithm (Print Sub-array - all Negative Input)

This is a modified form of the original Kadane's Algorithm and also works for all negative array input.

There are three changes -

**1)** Initialize variables with the **0th element** and start the loop from the **1st** element.

**2)** While calculating **"maxEndingHere"**, compare it with the current element **ar[i]** instead of **"0"** and assign **maxEndingHere=ar[i]** instead of **maxEndingHere=0**.

**3)** When **"maxEndingHere < arr[i]"** assign **"i" **instead of **"i+1"** to variable **"newStart"**.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.

### Method 3: Kadane's Algorithm (Original)

We can solve this problem with Kadane's Algorithm, the algorithm requires **at least one positive number**, so all negative array is invalid input.

def max_subarray(numbers): best_sum = 0 current_sum = 0 for x in numbers: current_sum = max(0, current_sum + x) best_sum = max(best_sum, current_sum) return best_sum

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.

### Method 4: Kadane's Algorithm (All Negative Input)

This version of Kadane's Algorithm also works with all negative elements array as input.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(1)**.