Dada una array arr[] que contiene n enteros. El problema es encontrar la longitud del subarreglo que tiene suma máxima. Si existen dos o más subarreglos con suma máxima, imprima la longitud del subarreglo más largo.
Ejemplos:
Input : arr[] = {5, -2, -1, 3, -4}
Output : 4
There are two subarrays with maximum sum:
First is {5}
Second is {5, -2, -1, 3}
Therefore longest one is of length 4.
Input : arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output : 5
The subarray is {4, -1, -2, 1, 5}
Enfoque: Los siguientes son los pasos:
- Encuentre el subarreglo contiguo de suma máxima . Sea esta suma maxSum .
- Encuentre la longitud del subarreglo más largo que tenga una suma igual a maxSum . Consulte esta publicación.
C++
// C++ implementation to find the length of the longest
// subarray having maximum sum
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum sum that
// exists in a subarray
int maxSubArraySum(int arr[], int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++) {
curr_max = max(arr[i], curr_max + arr[i]);
max_so_far = max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of longest
// subarray having sum k
int lenOfLongSubarrWithGivenSum(int arr[], int n, int k)
{
// unordered_map 'um' implemented
// as hash table
unordered_map<int, int> um;
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (um.find(sum) == um.end())
um[sum] = i;
// check if 'sum-k' is present in 'um'
// or not
if (um.find(sum - k) != um.end()) {
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// function to find the length of the longest
// subarray having maximum sum
int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
int main()
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of longest subarray having maximum sum = "
<< lenLongSubarrWithMaxSum(arr, n);
return 0;
}
Java
// Java implementation to find
// the length of the longest
// subarray having maximum sum
import java.util.*;
class GFG
{
// function to find the
// maximum sum that
// exists in a subarray
static int maxSubArraySum(int arr[],
int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++)
{
curr_max = Math.max(arr[i],
curr_max + arr[i]);
max_so_far = Math.max(max_so_far,
curr_max);
}
return max_so_far;
}
// function to find the
// length of longest
// subarray having sum k
static int lenOfLongSubarrWithGivenSum(int arr[],
int n, int k)
{
// unordered_map 'um' implemented
// as hash table
HashMap<Integer,
Integer> um = new HashMap<Integer,
Integer>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// accumulate sum
sum += arr[i];
// when subarray starts
// from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if
// it is not present in 'um'
if (um.containsKey(sum))
um.put(sum, i);
// check if 'sum-k' is present
// in 'um' or not
if (um.containsKey(sum - k))
{
// update maxLength
if (maxLen < (i - um.get(sum - k)))
maxLen = i - um.get(sum - k);
}
}
// required maximum length
return maxLen;
}
// function to find the length
// of the longest subarray
// having maximum sum
static int lenLongSubarrWithMaxSum(int arr[], int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 5, -2, -1, 3, -4 };
int n = arr.length;
System.out.println("Length of longest subarray " +
"having maximum sum = " +
lenLongSubarrWithMaxSum(arr, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation to find the length
# of the longest subarray having maximum sum
# function to find the maximum sum that
# exists in a subarray
def maxSubArraySum(arr, size):
max_so_far = arr[0]
curr_max = arr[0]
for i in range(1,size):
curr_max = max(arr[i], curr_max + arr[i])
max_so_far = max(max_so_far, curr_max)
return max_so_far
# function to find the length of longest
# subarray having sum k
def lenOfLongSubarrWithGivenSum(arr, n, k):
# unordered_map 'um' implemented
# as hash table
um = dict()
Sum, maxLen = 0, 0
# traverse the given array
for i in range(n):
# accumulate Sum
Sum += arr[i]
# when subarray starts from index '0'
if (Sum == k):
maxLen = i + 1
# make an entry for 'Sum' if it is
# not present in 'um'
if (Sum not in um.keys()):
um[Sum] = i
# check if 'Sum-k' is present in 'um'
# or not
if (Sum in um.keys()):
# update maxLength
if ((Sum - k) in um.keys() and
maxLen < (i - um[Sum - k])):
maxLen = i - um[Sum - k]
# required maximum length
return maxLen
# function to find the length of the longest
# subarray having maximum Sum
def lenLongSubarrWithMaxSum(arr, n):
maxSum = maxSubArraySum(arr, n)
return lenOfLongSubarrWithGivenSum(arr, n, maxSum)
# Driver Code
arr = [5, -2, -1, 3, -4]
n = len(arr)
print("Length of longest subarray having maximum sum = ",
lenLongSubarrWithMaxSum(arr, n))
# This code is contributed by mohit kumar
C#
// C# implementation to find
// the length of the longest
// subarray having maximum sum
using System;
using System.Collections.Generic;
public class GFG{
// function to find the
// maximum sum that
// exists in a subarray
static int maxSubArraySum(int []arr,
int size)
{
int max_so_far = arr[0];
int curr_max = arr[0];
for (int i = 1; i < size; i++)
{
curr_max = Math.Max(arr[i],
curr_max + arr[i]);
max_so_far = Math.Max(max_so_far,
curr_max);
}
return max_so_far;
}
// function to find the
// length of longest
// subarray having sum k
static int lenOfLongSubarrWithGivenSum(int []arr,
int n, int k)
{
// unordered_map 'um' implemented
// as hash table
Dictionary<int,
int> um = new Dictionary<int,
int>();
int sum = 0, maxLen = 0;
// traverse the given array
for (int i = 0; i < n; i++)
{
// accumulate sum
sum += arr[i];
// when subarray starts
// from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if
// it is not present in 'um'
if (um.ContainsKey(sum))
um.Add(sum, i);
// check if 'sum-k' is present
// in 'um' or not
if (um.ContainsKey(sum - k))
{
// update maxLength
if (maxLen < (i - um[sum - k]))
maxLen = i - um[sum - k];
}
}
// required maximum length
return maxLen;
}
// function to find the length
// of the longest subarray
// having maximum sum
static int lenLongSubarrWithMaxSum(int []arr, int n)
{
int maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver Code
public static void Main()
{
int []arr = { 5, -2, -1, 3, -4 };
int n = arr.Length;
Console.WriteLine("Length of longest subarray " +
"having maximum sum = " +
lenLongSubarrWithMaxSum(arr, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation to find the length of the longest
// subarray having maximum sum
// function to find the maximum sum that
// exists in a subarray
function maxSubArraySum(arr, size)
{
var max_so_far = arr[0];
var curr_max = arr[0];
for (var i = 1; i < size; i++) {
curr_max = Math.max(arr[i], curr_max + arr[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
// function to find the length of longest
// subarray having sum k
function lenOfLongSubarrWithGivenSum( arr, n, k)
{
// unordered_map 'um' implemented
// as hash table
var um = new Map();
var sum = 0, maxLen = 0;
// traverse the given array
for (var i = 0; i < n; i++) {
// accumulate sum
sum += arr[i];
// when subarray starts from index '0'
if (sum == k)
maxLen = i + 1;
// make an entry for 'sum' if it is
// not present in 'um'
if (!um.has(sum))
um.set(sum, i);
// check if 'sum-k' is present in 'um'
// or not
if (um.has(sum - k)) {
// update maxLength
if (maxLen < (i - um.get(sum-k)))
maxLen = i - um.get(sum-k)
}
}
// required maximum length
return maxLen;
}
// function to find the length of the longest
// subarray having maximum sum
function lenLongSubarrWithMaxSum(arr, n)
{
var maxSum = maxSubArraySum(arr, n);
return lenOfLongSubarrWithGivenSum(arr, n, maxSum);
}
// Driver program to test above
var arr = [5, -2, -1, 3, -4];
var n = arr.length;
document.write( "Length of longest subarray having maximum sum = "
+ lenLongSubarrWithMaxSum(arr, n));
// This code is contributed by rrrtnx.
</script>
Producción:
Length of longest subarray having maximum sum = 4
Complejidad temporal: O(n).
Espacio Auxiliar: O(n).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA