Largest Sum Contiguous SubArray in Java
Largest Sum Contiguous Subarray in Java
Here, in this page we will discuss the program to find the largest sum contiguous subarray in Java. We will discuss 3 different ways in this page for finding such subarray.
Go through this page get to know about Largest Sum Contiguous SubArray, how it is implemented through Java with different methods, their space and time complexity and other details related to its applications in real world.
Largest Sum Contiguous Sub Array in Java
Largest Sum Contiguous Sub Array
- Largest Sum Contiguous Subarray problem is one of the most classic and fundamental problems in computer science.
- Problem of finding the largest sum contiguous subarray in a given array involves identifying a subarray within the array that has the highest sum of its elements.
- This means we are searching for a continuous subarray in the given array that has the maximum possible sum.
It finds application in areas such as:
- Financial analysis (maximum profit segment)
- Signal processing
- Machine learning (feature value maximization)
- Competitive programming and interviews
- Given an array of integers (which may include negative numbers), the task is to find the contiguous subarray (containing at least one number) which has the largest sum.
This problem is famously known as the Kadane’s Algorithm problem, named after its creator Jay Kadane.
For example, consider the following array:
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
The largest sum contiguous subarray in this array is [4, -1, -2, 1, 5], which has a sum of 7.
And Problem of finding the largest sum contiguous subarray has a well-known algorithm called Kadane’s algorithm. The algorithm has a time complexity of O(n) and can be easily implemented in Java.
Example Problem Statement:
Given: An integer array arr[] of size n.
Find: The contiguous subarray (containing at least one element) with the maximum sum and return its sum.
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 Explanation: The contiguous subarray [4, -1, 2, 1] has the largest sum = 6.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Methods to Solve Largest Sum Contiguous SubArray in Java
Method 1 : Brute Force Approach.
Method 2 : Using Kadane’s Algorithm
Method 3: Kadane’s Algorithm with Index Tracking
Method 1 : Brute Force Approach
- Declare a variable say res = INT_MIN.
- Run a loop from index 0 to n.
- Declare a variable sum = 0;
- Run a nested loop from index i to n.
- Set sum += arr[j].
- And res = max(res, sum)
- After Complete Iteration print res.
Space Complexity :O(1)
Method 1 : Brute Force Approach
Try every possible subarray and calculate its sum. Keep track of the maximum sum.
public class LargestSumSubarray {
static int maxSubArrayBruteForce(int[] nums) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
int currSum = 0;
for (int j = i; j < nums.length; j++) {
currSum += nums[j];
maxSum = Math.max(maxSum, currSum);
}
}
return maxSum;
}
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum Sum: " + maxSubArrayBruteForce(arr));
}
}
Output:
Maximum Sum: 6
Largest Sum Contiguous Sub Array in Java
Method 2 : Using Kadane’s Algorithm
- Create variable say max_sum that hold the required maximum sum of subarray and curr_sum and initialize max_sum with INT_MIN and curr_sum with 0.
- Now, iterate over the array, and for every ith value of the array, add it to curr_sum, and compare it with max_sum like,
- if(max_sum < curr_sum)
max_sum = curr_sum. - Now, check if curr_sum <0 then set curr_sum to 0.
- After complete iteration we will get the result that store in max_sum variable.
Space Complexity : O(1)
Kadane’s algorithm is a dynamic programming approach that runs in linear time.
1. Initialize two variables:
- maxSoFar (stores the result)
- maxEndingHere (tracks the current subarray sum)
2. At each step:
- Add the current element to maxEndingHere.
- If maxEndingHere becomes less than the current element, start a new subarray from current.
- Update maxSoFar with the maximum of itself and maxEndingHere.
public class LargestSumSubarray {
static int maxSubArrayKadane(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum Sum using Kadane's Algorithm: " + maxSubArrayKadane(arr));
}
}
Output:
Maximum Sum using Kadane's Algorithm: 6
Largest Sum Contiguous Sub Array in Java Programming
Method 3: Kadane’s Algorithm with Index Tracking
Purpose: Retrieve not just the max sum, but also the actual subarray.
import java.util.Arrays;
public class LargestSumSubarray {
static int[] kadaneWithIndices(int[] nums) {
int maxSoFar = nums[0], maxEndingHere = nums[0];
int start = 0, end = 0, s = 0;
for (int i = 1; i < nums.length; i++) { if (nums[i] > maxEndingHere + nums[i]) {
maxEndingHere = nums[i];
s = i;
} else {
maxEndingHere += nums[i];
}
if (maxEndingHere > maxSoFar) {
maxSoFar = maxEndingHere;
start = s;
end = i;
}
}
return Arrays.copyOfRange(nums, start, end + 1);
}
public static void main(String[] args) {
int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int[] result = kadaneWithIndices(arr);
System.out.println("Max Sum Subarray: " + Arrays.toString(result));
}
}
Output:
Maximum Sum using Kadane's Algorithm: 6 Max Sum Subarray: [4, -1, 2, 1]
Time Complexity: O(n)
Applications of Largest Sum Subarray
- Financial Data Analysis: Maximize gain over a period (e.g., stock prices).
- Temperature/Rainfall Monitoring: Find maximum surge/drop within consecutive days.
- Audio/Signal Processing: Identify high intensity frequency bursts.
- Gaming: Determine best score streak.
- Machine Learning: Feature extraction from continuous data points.
Conclusion
- Largest Sum Contiguous Subarray problem elegantly demonstrates how greedy strategies and dynamic programming can solve seemingly complex problems efficiently.
- Kadane’s algorithm is not only optimal but also a foundational technique that applies to many real world scenarios.
- Whether you’re preparing for coding interviews, building analytical software, or just exploring algorithmic patterns, this problem is an essential one to master.
Learn DSA
FAQ's related to Largest Sum Contiguous Sub Array
Answer:
Kadane’s Algorithm is based on the idea of tracking the maximum sum of subarrays ending at each position.
At each index, it decides whether to:
- Extend the previous subarray, or
- Start a new subarray from the current element.
- It efficiently computes the maximum subarray sum in O(n) time without needing nested loops.
Answer:
Yes. Kadane’s Algorithm works even if all elements are negative. In that case, the result will be the largest (least negative) element. However, care must be taken to initialize maxSoFar and maxEndingHere with the first element of the array, not zero.
Answer:
- You can modify Kadane’s Algorithm to store start and end indices of the maximum sum subarray.
- By tracking when a new subarray starts and when the maximum is updated, you can reconstruct the subarray using those indices.
Answer:
- Kadane’s Algorithm is faster. Instead of checking all possible subarrays (which takes a long time), it keeps track of the best sum as it goes through the array once.
- This makes it much quicker and more efficient, especially with large arrays.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scn=new Scanner(System.in);
int n=scn.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=scn.nextInt();
}
int os=0,cs=0;
for(int i=0;i=0){
cs+=arr[i];
}
else{
cs=arr[i];
}
os=Math.max(os,cs);
}
System.out.print(“Maximum sum of array is “+os);
}
}
// Online Java Compiler
// Use this editor to write, compile and run your Java code online
class HelloWorld {
public static void main(String[] args) {
int a[]={-2,1,-3,4,-1,2,1,-5,4};
int sum=0;
int max=a[0];
for(int i=1;imax)
max=a[i];
}
for(int i=0;i<a.length;i++)
{
if(sum+a[i]<0)
sum=0;
else
{
sum=sum+a[i];
max=Math.max(sum,max);
}
}
System.out.print(max);
}
}
import java.io.*;
public class Largest_Sum_Contiguous_SubArray_in_Java {
public static int largest_sum(int[] arr){
int curr_sum=arr[0];
int max_sum=arr[0];
for(int i=0;i< arr.length;i++){
curr_sum=Math.max(curr_sum,curr_sum+arr[i]);
max_sum=Math.max(curr_sum,max_sum);
}
return max_sum;
}
public static void main(String[] args) {
int a[] = {-2,1,-3,4,-1,2,1,-5,4};
// int n = a.length;
int maxsum = largest_sum(a);
System.out.println(
maxsum);
}
}