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 two different ways in this page for finding such subarray.Largest Sum Contiguous Sub-Array in Java
The 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.
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. The 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.
Method Discussed :
- Method 1 : Brute Force Approach.
- Method 2 : Using Kadane’s Algorithm
Method 1 :
- 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.
Time and Space Complexity :
- Time Complexity : O(n2)
- Space Complexity : O(1)
Method 1 : Code in Java
Run
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = arr.length;
int res = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
res = Math.max(sum, res);
}
}
System.out.println(res);
}
}
Output
7
Method 2 :
- 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 comapre 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.
Time and Space Complexity :
- Time Complexity : O(n)
- Space Complexity : O(1)
Method 2 : Code in Java
Run
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = arr.length;
int max_sum = Integer.MIN_VALUE, curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
if (max_sum < curr_sum)
max_sum = curr_sum;
if (curr_sum < 0)
curr_sum = 0;
}
System.out.println(max_sum);
}
}
Output
7
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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
Arrays
- Introduction to Arrays – C | C++ | Java
- Introduction to 2-D Arrays – C | C++ | Java
- Sorting of Array – C | C++ | Java
- Array Rotation – C | C++ | Java
- Reverse an array or string- C | C++ | Java
- Find pairs in array with given sum – C | C++ | Java
- Sort the array in Waveform – C | C++ | Java
- Majority Element in Array – C | C++ | Java
- Boyer-Moore’s Voting Algorithm – C | C++ | Java
- K-pairs with smallest sum in 2 arrays – C | C++ | Java
- Largest Sum Contigous SubArray – C | C++ | Java
- Maximum Average Sub-array of K length – C | C++ | Java
- Size of sub-array with max sum – C | C++ | Java
- Sub-array with given sum – C | C++ | Java
- Triplet that sum to a given value – C | C++ | Java
- Segregate 0’s and 1’s in array – C | C++ | Java
- Segregate 0’s 1’s and 2’s in array – C | C++ | Java
- Sort elements in array by frequency – C | C++ | Java
- Finding pythagorean triplets in an array – C | C++ | Java
- Reorder array using given indexes – C | C++ | Java
- Merging two sorted arrays – C | C++ | Java
- Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
- Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java
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);
}
}