w3resource

Java: Find a contiguous subarray with largest sum from a given array of integers

Java Basic: Exercise-122 with Solution

Write a Java program to find a contiguous subarray with the largest sum from a given array of integers.
Note: In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
The subarray should contain one integer at least.

Pictorial Presentation:

Java Basic Exercises: Find a contiguous subarray with largest sum from a given array of integers

Sample Solution:

Java Code:

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        // Input array
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        // Find and print the maximum subarray sum
        System.out.print(max_SubArray(nums)); 
    }

    public static int max_SubArray(int[] nums) {
        // Check if the input array is empty
        if (nums.length < 1) {
            return 0;
        }
        // Initialize variables to track the maximum sum, its start and end indices
        int max = nums[0];
        int max_Begin = 0;
        int max_End = 0;
        int begin = 0;
        int end = 0;
        int sum = 0;
        
        while (end < nums.length) {
            // Update the current sum with the value at the current end index
            sum += nums[end];
            if (sum < 0) {
                // If the current sum becomes negative, reset it and update the beginning index
                sum = 0;
                begin = end + 1;
            } else {
                // If the current sum is greater than the maximum, update the maximum
                if (sum > max) {
                    max = sum;
                    max_Begin = begin;
                    max_End = end;
                }
            }
            end++;
        }
        // Return the maximum sum of the subarray
        return max;
    }
}

Sample Output:

6 

Flowchart:

Flowchart: Java exercises: Find a contiguous subarray with largest sum from a given array of integers

Java Code Editor:

Previous: Write a Java program to reverse a given linked list.
Next: Write a Java program to find the subarray with smallest sum from a given array of integers.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/java-exercises/basic/java-basic-exercise-122.php