Longest subarray having maximum sum | C ++ implementation to find the length of the longest subarray having maximum sum ; function to find the maximum sum that exists in a subarray ; function to find the length of longest subarray having sum k ; unordered_map ' um ' implemented as hash table ; traverse the given array ; accumulate sum ; when subarray starts from index '0' ; make an entry for ' sum ' if it is not present in ' um ' ; check if ' sum - k ' is present in ' um ' or not ; update maxLength ; required maximum length ; function to find the length of the longest subarray having maximum sum ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } int lenOfLongSubarrWithGivenSum ( int arr [ ] , int n , int k ) { unordered_map < int , int > um ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; if ( sum == k ) maxLen = i + 1 ; if ( um . find ( sum ) == um . end ( ) ) um [ sum ] = i ; if ( um . find ( sum - k ) != um . end ( ) ) { if ( maxLen < ( i - um [ sum - k ] ) ) maxLen = i - um [ sum - k ] ; } } return maxLen ; } int lenLongSubarrWithMaxSum ( int arr [ ] , int n ) { int maxSum = maxSubArraySum ( arr , n ) ; return lenOfLongSubarrWithGivenSum ( arr , n , maxSum ) ; } 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 ; }