logo
  • Programming
  • Testing
  • AI
  • Devops
  • Data Science
  • Design
  • Blog
  • Crypto Tools
  • Dev Feed
  • Login
Story
Follow @devglan

Write a Java program to find the largest sum of the contiguous subarray in a given Array

author-image   By Dhiraj,   20 June, 2020 0K

Write a Java program to find the largest sum of the contiguous subarray in a given Array. The given array might contain negative elements too and hence we need to find out a contiguous sub-array whose sum would be maximum.

The brute force approach would be to use a nested loop to find this subarray and the time-complexity for the same would be O(n^2) which is inefficient. This can be optimized to a time-complexity of O(n) with dynamic programming using Kadane’s algorithm.

This is one of the most asked interview programs for Java developers and we can solve many other problems using this particular algorithm such as maximum sum rectangle in a 2D matrix.

In this algorithm, we have two variables as bestSum and currentSum initialized to 0. For each iteration, we calculate the currentSum by adding the value present at the current index to the currentSum and update the bestSum with currentSum in case we find currentSum is greater than the bestSum. Else, the the current value of the best sum is the largest sum value so far.

Below is the sample java program for the same.

public class LargestSubArraySum {
    
    //print the sum of largest sub array
    public static void main(String[] args){
        int[] arr = {-1, 5, -50, -3, -90};
        int length = arr.length;
        int bestSum = 0;
        int currentSum = 0;
        for(int i =0; i < length; i++){
            currentSum = currentSum + arr[i];
            if(currentSum > bestSum){
                //Now, once the currentSum becomes more then bestSum the value of bestSum will be reset
                bestSum = currentSum;
            }else {
                //currentSum is less and hence reset the currentSum.
                currentSum  = 0;
            }
        }
        System.out.println(bestSum);
    }
}

Output

5

Above program prints the largest contiguous subarray sum of a given array. With a little tweak, it is also possible to print the start and end index of the sub array.

public static void largestSumSubArray(int[] array){
        int i = 0;
        int j = 0;
        int bestSum = 0;
        int currentSum = 0;
        for (int k = 0; k < array.length; k++){
            currentSum = currentSum + array[k];
            if (currentSum > bestSum){
                bestSum = currentSum;
                j = k;
            }else {
                currentSum = 0;
                if (k <= j){
                    i = k + 1;
                }
            }
        }
        System.out.println("Max sub array start at " + i + " end at " + j);
    }

Explanation

Click to Suggest Your Own Explanation

Other Similar Java Programs:

1 Java Program to test if given number is Armstrong or not
2 Java Program to test if a given number is Fibonacci or not
3 java program to find distinct word list from a file
4 Java program to find duplicate character from a string
5 Java Program to find middle index of array where both ends sum is equal
6 Java Program to find line with max character length in descending order in Java
7 Java Program to find max two numbers in an array
8 Java program to find max repeated words from a file
9 Java program to find sum of prime numbers
10 Java program to reverse a given number
11 Java program to find permutations of a given string
12 Java program to reverse a given string
13 Java program to find factorial of a given number
14 Java Program for Binary Search
15 Java Program to Add Two 2D Matrix
16 3 Ways to Check if Given Words are Anagram or not
17 Java Program to Find LCM of a Two Given Number
18 Check Given String is Rotation of Another String
19 Java Program To Check If A Given Number is A Perfect Number
20 Remove Common Characters From Given Strings
21 Find Second Largest Number in Array
22 Java Program To Find the Longest Palindrome Present in a String
23 Java Program to Reverse an Array in Place Without Using Any Second Array
24 Java Program to Print 1 To 10 Without Using Loop
25 Write a Java Program to Compare Files in Java
26 Java Program to Find missing Number in an Array
27 Java Program to Find First non Repeated Character in a String
28 Write a Java Program to Find Union and Intersection of Arrays in Java
29 Writing a Java program to rotate an array by d elements.
30 Write a Java program to rotate a matrix

If You Appreciate This, You Can Consider:

  • Like us at: Facebook or follow us at Twitter
  • Share this article on social media or with your teammates.

Suggest Explanation

The suggestion has been saved for review.Thanks for your effort.

{{errorMessage}}

Vertex

Devglan is one stop platform for all
programming tutorials and courses.

About Us

  • About Us
  • Contact Us
  • Submission Criteria
  • Privacy Policy

Quick Links

  • Home
  • Login / Join
  • Submit Your Story
  • Donate

Contact Us

Dhiraj
dhiraj@devglan.com

© 2020 Devglan. All rights reserved.