Tamaño del subarreglo con suma máxima

Se da un arreglo, encuentre la longitud del subarreglo que tiene la suma máxima.

Ejemplos: 

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

Este problema es principalmente una variación del problema de subarreglo contiguo de suma más grande .
La idea es actualizar el índice inicial cada vez que la suma que termina aquí sea menor que 0.

// C++ program to print length of the largest
// contiguous array sum
#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);
}
 
/*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 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 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# 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
// PHP program for Bresenham’s
// Line Generation Assumptions :
 
// 1) Line is drawn from
// left to right.
// 2) x1 < x2 and y1 < y2
// 3) Slope of the line is
// between 0 and 1.
// We draw a line from lower
// left to upper right.
 
// function for line generation
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";
 
    // Add slope to increment
    // angle formed
    $slope_error_new += $m_new;
 
    // Slope error reached limit,
    // time to increment y and
    // update slope error.
    if ($slope_error_new >= 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.
?>

<script>
 
// JavaScript program to print length
// of the largest contiguous array sum
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);
}
 
// Driver code
let a = [ -2, -3, 4, -1, -2, 1, 5, -3 ];
let n = a.length;
 
document.write(maxSubArraySum(a, n));
 
// This code is contributed by splevel62
 
</script>

5

Complejidad temporal: O(n).

Espacio Auxiliar: O(1)