Max circular sum (what is the error in it)

#1

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int a[] = new int[n];
for(int j =0;j<n;j++)
{
a[j]=sc.nextInt();
}
findSumOFCircular(a);
}

}

public static void findSumOFCircular(int a[]) {
	for(int i=0;i<a.length;i++)
	{
		a[i]=a[i]*(-1);
	}
	//now using the kadaens algo for finding the sum of highest 
	int i =0;
	int max_so_far=a[i];
	int max_ending_here =0;
	int start=0,s=0,e=0;
	for(i=0;i<a.length;i++)
	{
		max_ending_here=max_ending_here + a[i];
		if(max_so_far<max_ending_here) {
			max_so_far=max_ending_here;
			start =s;e=i;
		}
		if(max_ending_here<0) {
			max_ending_here=0;
			s=i+1;
		}
	}
	int sum =0;
	for(int j=0;j<a.length;j++)
	{
		a[i]=a[i]*(-1);
		
	}
	for(int j =0;j<a.length;i++)
	{
		sum =sum+a[j];
	}
	System.out.println(sum-max_so_far);
#2

HI,
Ide is not working so i had to post the code here … There were two errors … look for the comments … other than that the code has logical error.What you have done is a bit correct for non circular array . Circular array uses a modified kadane . In that you have to first calculate the max in normal given array and then multiply every element by -1 and then find max again and then subtract that from the sum . however here’s your corrected code but still it won’t work … so think correct solution.

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int a[] = new int[n];
for (int j = 0; j < n; j++) {
a[j] = sc.nextInt();
}
findSumOFCircular(a);
}

}

public static void findSumOFCircular(int a[]) {
    for (int i = 0; i < a.length; i++) {
        a[i] = a[i] * (-1);
    }
    // now using the kadaens algo for finding the sum of highest
    int i = 0;
    int max_so_far = a[i];
    int max_ending_here = 0;
    int start = 0, s = 0, e = 0;
    for (i = 0; i < a.length; i++) {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here) {
            max_so_far = max_ending_here;
            start = s;
            e = i;
        }
        if (max_ending_here < 0) {
            max_ending_here = 0;
            s = i + 1;
        }
    }
    int sum = 0;
    for (int j = 0; j < a.length; j++) {  
        a[j] = a[j] * (-1); //You were using i as index

    }
    for (int j = 0; j < a.length; j++) {  //Here it was i++
        sum = sum + a[j];
    }
    System.out.println(sum - max_so_far);
}

}

#3
#4

as you said i did the solution still giving wrong ans

#5

Hi @vikashkmr519,
You have to used a wrap function that will store initial sum and then subtract from that.
Look for comment in the below code.

#6

System.out.println(wrap>straightSum?wrap:straightSum); ,i didnt understood this line plss explain me in detail

#7

This line is the short form of if(wrap>straightSum){ system.out.println(wrap)}else{system.out.println(straightSum)}