Maximum subarray sum

#1

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–)
{
int n=sc.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){

	arr[i]=sc.nextInt();
}
Arrays.fill(arr,0);	
	sum_arr=arr[0];
	for(int i=1;i<n;i++)
	sum_arr[i]=sum_arr[i-1]+arr[i];
	int sum=0,current_sum;
	for(int i=0;i<n;i++)
{
	for(int j=i;j<n;j++)
	{
		current_sum=0;
		current_sum=(sum_arr[j]-sum_arr[i-1]);
		if(current_sum>sum)
		sum=current_sum;

	}
}
System.out.println(sum);	

}

}
}
plz send the corrected code

#2

@karthik1989photos,

Buddy, I will share the suggested approach for this question. You can try implementing that first.

Algo:

1.Take two variables one for storing local max sum(max-ending-here) and global max sum(max-so-far).
2.Iterate over each each element of the array say a.

  2.1 max_ending_here = max_ending_here + a[i]
  2.2 if(max_ending_here < 0)   
        max_ending_here = 0
  2.3 if(max_so_far < max_ending_here)
        max_so_far = max_ending_here

3.max-so-far is the required max sum of contiguous subarray.

#3

import java.util.*;
public class Main
{
public static int maxSubArraySum(int[] a,int size){
int maxsofar=0,maxendinghere=0;
for(int i=0;i<size;i++){
maxendinghere=maxendinghere+a[i];
if(maxendinghere<0){
maxendinghere=0;
}
if(maxsofar<maxendinghere){
maxsofar=maxendinghere;
}
}
return maxsofar;
}
public static void main(String[] args){
int[] a={1,2,3,4,-10};
System.out.println(maxSubArraySum(a,5));
}
}
i tried but my testcases not running

#4

@karthik1989photos,
The maxSubArraySum function is correct. You need to take the input of the array as well and not use a defined input for every test care.

#5

@karthik1989photos,
Take input of array and pass the array to the maxSubArraySum function.

Don’t define a particular array for all the test cases.

#6

import java.util.*;
public class Main
{
public static int maxSum(int[] a,int size){
int maxsofar=0,maxendinghere=0;
for(int i=0;i<size;i++){
maxendinghere=maxendinghere+a[i];
if(maxendinghere<0){
maxendinghere=0;
}
if(maxsofar<maxendinghere){
maxsofar=maxendinghere;
}
}
return maxsofar;
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
if(n<-1000000000&&n>1000000000){
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
}
int p;
p=maxSum(a,n);
System.out.println§;
}
}
}
i am unable to solve please provide the solution

#7

@karthik1989photos,

https://ide.codingblocks.com/s/266581 corrected code.

You had to take input of the number of testcases as well. :slight_smile:

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.