Size of sub-array with max sum 

January 29, 2021

size of sub array with max sum

Size of sub-array with a max sum in Java

Problem statement:

An array is given, find the length of the subarray having a maximum sum.

Input :

arr[ ] = { -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}.

NOTE :

This problem is mainly a variation of the Largest Sum Contiguous Subarray Problem.

Refer to the link above to get a better understanding.

Algorithm:

  • START
  • CALL FUNCTION maxsubArraySum
initialize variables
int maxsofar = Integer.MIN_VALUE, 
        maxend = 0,start = 0, 
        end = 0, s = 0; 

        for (int i = 0; i < n; i++) 
        { 
            maxend += arr[i]; 

            if (maxsofar < maxend) 
            { 
                maxsofar = maxend; 
                start = s; 
                end = i; 
            } 

            if (maxend < 0) 
            { 
                maxend = 0; 
                s = i + 1; 
            } 
        } 
        return (end – start + 1); 
  • END

JAVA CODE :

// Java program to print length of the largest sum

class prepinsta { 

    static int maxSubArraySum(int arr[], int n) 
    { 
        int maxsofar = Integer.MIN_VALUE, 
        maxend = 0,start = 0, 
        end = 0, s = 0; 

        for (int i = 0; i < n; i++) 
        { 
            maxend += arr[i]; 

            if (maxsofar < maxend) 
            { 
                maxsofar = maxend; 
                start = s; 
                end = i; 
            } 

            if (maxend < 0) 
            { 
                maxend = 0; 
                s = i + 1; 
            } 
        } 
        return (end – start + 1); 
    } 

 
    public static void main(String[] args) 
    { 
        int arr[] = { –2, –3, 4, –1, –2, 1, 5, –3 }; 
        int n = arr.length; 
        System.out.println(“maximum subarray sum is “+maxSubArraySum(arr, n)); 
    } 
} 
Output:
maximum subarray sum is 5