Given an array arr[] of size N, the task is to find the length of the subarray having maximum sum.
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}.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h>
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);
}
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
import java.io.*;
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 );
}
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
from sys import maxsize
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 )
a = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ]
print (maxSubArraySum(a, len (a)))
|
C#
using System;
class GFG {
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);
}
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));
}
}
|
PHP
<?php
function bresenham( $x1 , $y1 , $x2 , $y2 )
{
$m_new = 2 * ( $y2 - $y1 );
$slope_error_new = $m_new - ( $x2 - $x1 );
for ( $x = $x1 , $y = $y1 ; $x <= $x2 ; $x ++)
{
echo "(" , $x , "," , $y , ")\n" ;
$slope_error_new += $m_new ;
if ( $slope_error_new >= 0)
{
$y ++;
$slope_error_new -= 2 * ( $x2 - $x1 );
}
}
}
$x1 = 3; $y1 = 2; $x2 = 15; $y2 = 5;
bresenham( $x1 , $y1 , $x2 , $y2 );
?>
|
Javascript
<script>
function maxSubArraySum(a, size)
{
let max_so_far = Number.MIN_VALUE,
max_ending_here = 0,start = 0,
end = 0, s = 0;
for (let 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);
}
let a = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
let n = a.length;
document.write(maxSubArraySum(a, n));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach#2: Using Kadane’s algorithm
This approach implements the Kadane’s algorithm to find the maximum subarray sum and returns the size of the subarray with maximum sum.
Algorithm
1. Initialize max_sum, current_sum, start, end, max_start, and max_end to the first element of the array.
2. Iterate through the array from the second element.
3. If the current element is greater than the sum of the current element and current_sum, update start to the current index.
4. Update current_sum as the maximum of the current element and the sum of current element and current_sum.
5. If current_sum is greater than max_sum, update max_sum, end to the current index, and max_start and max_end to start and end respectively.
6. Return max_end – max_start + 1 as the size of the subarray with maximum sum.
C++
#include <bits/stdc++.h>
using namespace std;
int max_subarray_sum(vector< int >& a)
{
int n = a.size();
int max_sum = a[0];
int current_sum = a[0];
int start = 0;
int end = 0;
int max_start = 0;
int max_end = 0;
for ( int i = 1; i < n; i++) {
if (a[i] > current_sum + a[i]) {
start = i;
}
current_sum = max(a[i], current_sum + a[i]);
if (current_sum > max_sum) {
max_sum = current_sum;
end = i;
max_start = start;
max_end = end;
}
}
return max_end - max_start + 1;
}
int main()
{
vector< int > a{ -2, -3, 4, -1, -2, 1, 5, -3 };
cout << max_subarray_sum(a) << endl;
return 0;
}
|
Java
import java.util.*;
public class Main
{
static int maxSubarraySum(List<Integer> a) {
int n = a.size();
int max_sum = a.get( 0 );
int current_sum = a.get( 0 );
int start = 0 ;
int end = 0 ;
int max_start = 0 ;
int max_end = 0 ;
for ( int i = 1 ; i < n; i++) {
if (a.get(i) > current_sum + a.get(i)) {
start = i;
}
current_sum = Math.max(a.get(i), current_sum + a.get(i));
if (current_sum > max_sum) {
max_sum = current_sum;
end = i;
max_start = start;
max_end = end;
}
}
return max_end - max_start + 1 ;
}
public static void main(String[] args) {
List<Integer> a = Arrays.asList(- 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 );
System.out.println(maxSubarraySum(a));
}
}
|
Python3
def max_subarray_sum(a):
n = len (a)
max_sum = a[ 0 ]
current_sum = a[ 0 ]
start = 0
end = 0
max_start = 0
max_end = 0
for i in range ( 1 , n):
if a[i] > current_sum + a[i]:
start = i
current_sum = max (a[i], current_sum + a[i])
if current_sum > max_sum:
max_sum = current_sum
end = i
max_start = start
max_end = end
return max_end - max_start + 1
a = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ]
print (max_subarray_sum(a))
|
C#
using System;
using System.Collections.Generic;
public class MaxSubarraySum {
public static int FindMaxSubarraySum(List< int > a) {
int n = a.Count;
int maxSum = a[0];
int currentSum = a[0];
int start = 0;
int end = 0;
int maxStart = 0;
int maxEnd = 0;
for ( int i = 1; i < n; i++) {
if (a[i] > currentSum + a[i]) {
start = i;
}
currentSum = Math.Max(a[i], currentSum + a[i]);
if (currentSum > maxSum) {
maxSum = currentSum;
end = i;
maxStart = start;
maxEnd = end;
}
}
return maxEnd - maxStart + 1;
}
public static void Main() {
List< int > a = new List< int > { -2, -3, 4, -1, -2, 1, 5, -3 };
Console.WriteLine(FindMaxSubarraySum(a));
}
}
|
Javascript
function max_subarray_sum(a) {
const n = a.length;
let max_sum = a[0];
let current_sum = a[0];
let start = 0;
let end = 0;
let max_start = 0;
let max_end = 0;
for (let i = 1; i < n; i++) {
if (a[i] > current_sum + a[i]) {
start = i;
}
current_sum = Math.max(a[i], current_sum + a[i]);
if (current_sum > max_sum) {
max_sum = current_sum;
end = i;
max_start = start;
max_end = end;
}
}
return max_end - max_start + 1;
}
const a = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(max_subarray_sum(a));
|
Time Complexity: O(n), where n is length of array
Auxiliary Space: O(1)
Note: The above code assumes that there is at least one positive element in the array. If all the elements are negative, the code needs to be modified to return the maximum element in the array.
Contact Us