Longest subarray having maximum sum | Java 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 Code
import java . util . * ; class GFG { 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 ; } static int lenOfLongSubarrWithGivenSum ( int arr [ ] , int n , int k ) { HashMap < Integer , Integer > um = new HashMap < Integer , Integer > ( ) ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; if ( sum == k ) maxLen = i + 1 ; if ( um . containsKey ( sum ) ) um . put ( sum , i ) ; if ( um . containsKey ( sum - k ) ) { if ( maxLen < ( i - um . get ( sum - k ) ) ) maxLen = i - um . get ( sum - k ) ; } } return maxLen ; } static int lenLongSubarrWithMaxSum ( int arr [ ] , int n ) { int maxSum = maxSubArraySum ( arr , n ) ; return lenOfLongSubarrWithGivenSum ( arr , n , maxSum ) ; } 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 ) ) ; } }