# Size of The Subarray With Maximum Sum

An array is given, find length of the subarray having maximum sum.

Examples :

```Input :  a[] = {1, -2, 1, 1, -2, 1}
Output : Length of the subarray is 2
Explanation: Subarray with consecutive elements
and maximum sum will be {1, 1}. So length is 2

Input : ar[] = { -2, -3, 4, -1, -2, 1, 5, -3 }
Output : Length of the subarray is 5
Explanation: Subarray with consecutive elements
and maximum sum will be {4, -1, -2, 1, 5}.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

This problem is mainly a variation of Largest Sum Contiguous Subarray Problem.

The idea is to update starting index whenever sum ending here becomes less than 0.

## C++

 `// C++ program to print length of the largest  ` `// contiguous array sum ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `int` `maxSubArraySum(``int` `a[], ``int` `size) ` `{ ` `    ``int` `max_so_far = INT_MIN, max_ending_here = 0, ` `       ``start =0, end = 0, s=0; ` ` `  `    ``for` `(``int` `i=0; i< size; i++ ) ` `    ``{ ` `        ``max_ending_here += a[i]; ` ` `  `        ``if` `(max_so_far < max_ending_here) ` `        ``{ ` `            ``max_so_far = max_ending_here; ` `            ``start = s; ` `            ``end = i; ` `        ``} ` ` `  `        ``if` `(max_ending_here < 0) ` `        ``{ ` `            ``max_ending_here = 0; ` `            ``s = i + 1; ` `        ``} ` `    ``} ` `     `  `    ``return` `(end - start + 1); ` `} ` ` `  `/*Driver program to test maxSubArraySum*/` `int` `main() ` `{ ` `    ``int` `a[] = {-2, -3, 4, -1, -2, 1, 5, -3}; ` `    ``int` `n = ``sizeof``(a)/``sizeof``(a[0]); ` `    ``cout << maxSubArraySum(a, n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to print length of the largest  ` `// contiguous array sum ` `class` `GFG { ` ` `  `    ``static` `int` `maxSubArraySum(``int` `a[], ``int` `size) ` `    ``{ ` `        ``int` `max_so_far = Integer.MIN_VALUE, ` `        ``max_ending_here = ``0``,start = ``0``, ` `        ``end = ``0``, s = ``0``; ` ` `  `        ``for` `(``int` `i = ``0``; i < size; i++)  ` `        ``{ ` `            ``max_ending_here += a[i]; ` ` `  `            ``if` `(max_so_far < max_ending_here)  ` `            ``{ ` `                ``max_so_far = max_ending_here; ` `                ``start = s; ` `                ``end = i; ` `            ``} ` ` `  `            ``if` `(max_ending_here < ``0``)  ` `            ``{ ` `                ``max_ending_here = ``0``; ` `                ``s = i + ``1``; ` `            ``} ` `        ``} ` `        ``return` `(end - start + ``1``); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `a[] = { -``2``, -``3``, ``4``, -``1``, -``2``, ``1``, ``5``, -``3` `}; ` `        ``int` `n = a.length; ` `        ``System.out.println(maxSubArraySum(a, n)); ` `    ``} ` `} `

## Python3

 `# Python program to print largest contiguous array sum ` ` `  `from` `sys ``import` `maxsize ` ` `  `# Function to find the maximum contiguous subarray ` `# and print its starting and end index ` `def` `maxSubArraySum(a,size): ` ` `  `    ``max_so_far ``=` `-``maxsize ``-` `1` `    ``max_ending_here ``=` `0` `    ``start ``=` `0` `    ``end ``=` `0` `    ``s ``=` `0` ` `  `    ``for` `i ``in` `range``(``0``,size): ` ` `  `        ``max_ending_here ``+``=` `a[i] ` ` `  `        ``if` `max_so_far < max_ending_here: ` `            ``max_so_far ``=` `max_ending_here ` `            ``start ``=` `s ` `            ``end ``=` `i ` ` `  `        ``if` `max_ending_here < ``0``: ` `            ``max_ending_here ``=` `0` `            ``s ``=` `i``+``1` ` `  `    ``return` `(end ``-` `start ``+` `1``) ` ` `  `# Driver program to test maxSubArraySum ` `a ``=` `[``-``2``, ``-``3``, ``4``, ``-``1``, ``-``2``, ``1``, ``5``, ``-``3``] ` `print``(maxSubArraySum(a,``len``(a))) `

## C#

 `// C# program to print length of the  ` `// largest contiguous array sum ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Function to find maximum subarray sum ` `    ``static` `int` `maxSubArraySum(``int` `[]a, ``int` `size) ` `    ``{ ` `        ``int` `max_so_far = ``int``.MinValue, ` `        ``max_ending_here = 0,start = 0, ` `        ``end = 0, s = 0; ` ` `  `        ``for` `(``int` `i = 0; i < size; i++)  ` `        ``{ ` `            ``max_ending_here += a[i]; ` ` `  `            ``if` `(max_so_far < max_ending_here)  ` `            ``{ ` `                ``max_so_far = max_ending_here; ` `                ``start = s; ` `                ``end = i; ` `            ``} ` ` `  `            ``if` `(max_ending_here < 0)  ` `            ``{ ` `                ``max_ending_here = 0; ` `                ``s = i + 1; ` `            ``} ` `        ``} ` `        ``return` `(end - start + 1); ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main(String[] args) ` `    ``{ ` `        ``int` `[]a = {-2, -3, 4, -1, -2, 1, 5, -3}; ` `        ``int` `n = a.Length; ` `        ``Console.Write(maxSubArraySum(a, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by parashar... `

## PHP

 `= 0) ` `    ``{ ` `        ``\$y``++; ` `        ``\$slope_error_new` `-= 2 * (``\$x2` `- ``\$x1``); ` `    ``} ` `} ` `} ` ` `  `// Driver Code ` `\$x1` `= 3; ``\$y1` `= 2; ``\$x2` `= 15; ``\$y2` `= 5; ` `bresenham(``\$x1``, ``\$y1``, ``\$x2``, ``\$y2``); ` ` `  `// This code is contributed by nitin mittal. ` `?> `

Output :

```5
```