Java: Find the maximum sum of a contiguous subsequence from a given sequence of numbers

Last update on May 13 2025 12:58:57 (UTC/GMT +8 hours)

Maximum Sum of Contiguous Subsequence

Write a Java program to find the maximum sum of a contiguous subsequence from a given sequence of numbers a1, a2, a3, ... an. A subsequence of one element is also a continuous subsequence.

Input:
You can assume that 1 ≤ n ≤ 5000 and -100000 ≤ ai ≤ 100000.
Input numbers are separated by a space.
Input 0 to exit.

Visual Presentation:

Sample Solution:

Java Code:

// Importing necessary Java utilities for input
import java.util.*;

// Main class named "Main"
public class Main {
    // Main method to execute the program
	public static void main(String [] args) {
		// Creating a Scanner object for user input
		Scanner s = new Scanner(System.in);

		// Prompting the user to specify the number of integers to input
		System.out.println("How many integers would you like to input?");
		int n = s.nextInt();

		// Initializing variables for the maximum sum and the current accumulation
		int ans = -100000;
		int acc = 0;

		// Prompting the user to input the integers
		System.out.println("Input the integers:");

		// Looping through each input integer to find the maximum contiguous subsequence sum
		for (int i = 0; i < n; i++) {
			// Accumulating the current integer
			acc += s.nextInt();

			// Updating the maximum sum using Math.max function
			ans = Math.max(ans, acc);

			// Resetting the accumulation to 0 if it becomes negative
			if (acc < 0) acc = 0;
		}

		// Outputting the maximum sum of the contiguous subsequence
		System.out.println("Maximum sum of the said contiguous subsequence:");
		System.out.println(ans);
	}
} 

Sample Output:

How many integers would you like to input?
 5
Input the integers:
 25 61 35 42 66
Maximum sum of the said contiguous subsequence:
229

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to find the minimum sum of a contiguous subsequence in a given array.
• Write a Java program to compute the maximum product of a contiguous subsequence in an array.
• Write a Java program to determine the maximum sum of a contiguous subsequence using a divide and conquer approach.
• Write a Java program to find the maximum sum of a contiguous subsequence whose total is an even number.

Go to:

• Java Basic Part-II Programming Exercises Home ↩
• Java Exercises Home ↩

PREV : Test If Two Lines Are Parallel.
NEXT : Test Relationship Between Two Circles.

Java Code Editor:

Contribute your code and comments through Disqus.