Maximum sum of sub-array using Kadane's Algorithm in Java

Question

This is a problem statement from geeks for geeks (link : https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0 )

My code is working fine as per the Compile & test option. But when I try to submit, it throws error about failure for multiple test cases.

Could anyone help me with this?

CODE:

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;


public class Kadane

{
public static void main(String[]args) throws IOException,NumberFormatException

{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    System.out.println("Enter the number of test cases");
    int T = Integer.parseInt(br.readLine());

    for(int t=0 ; t<T ; t++)
    {
        int N,a=0;
        int sum1=0,maxsum=-2147483648,kadanesum=-2147483648;

        System.out.println("Enter the size of array : ");
        N =  Integer.parseInt(br.readLine());
        int arr[] = new int[N];

        System.out.println("Enter the array elements separated by space");
        String S = new String(br.readLine());
        String elem[] = S.split(" ");

        for(String e:elem)
        {
            arr[a] = Integer.parseInt(e);
            a++;
        }

        for(int i=0 ; i<N ; i++)
        {
            for(int j=i ; j<N ; j++)
            {
                sum1 = sum1 + arr[j];
                if(maxsum<sum1)
                {
                    maxsum=sum1;

                }
            }
            if(maxsum>kadanesum)
            {
                kadanesum=maxsum;
            }
            sum1=0;
            maxsum=-2147483648;
        }

        System.out.println("\tKadane Sum = " + kadanesum);

    }           
}
}

My code link : https://ide.geeksforgeeks.org/tXNHh28A0D

My input : 5(number of test cases)

3(array size)

1 2 3(array elements)

5

1 2 3 -2 5

10

2 9 3 -10 -20 34 28 -50 30 -1

7

4 5 -10 -50 3 9 8

8

8 9 8 -25 25 1 2

My output : Enter the number of test cases

Enter the size of array : Enter the array elements separated by space Kadane Sum = 6

Enter the size of array : Enter the array elements separated by space Kadane Sum = 9

Enter the size of array : Enter the array elements separated by space Kadane Sum = 62

Enter the size of array : Enter the array elements separated by space Kadane Sum = 20

Enter the size of array : Enter the array elements separated by space Kadane Sum = 28

I get the below error message when submitting my code :

Wrong Answer. !!!Wrong Answer Possibly your code doesn't work correctly for multiple test-cases (TCs). The first test case where your code failed:

Input:(As per website) 3 1 2 3

Its Correct output is: 6

I have used this same input in my input test cases(test case 1) and the output is same as expected.

Could anyone help me to optimize the code using StringBuffer?

@Ajay Coding websites don't want output as you have given them they just want the number most of the times, remove you lines where you have printed enter the size of the array, Enter the array elements...., it is also given in the problem statement as to what is the expected input and what is the expected output. You must follow those standards otherwise they reject your answer. — Rahul

Guillaume Guillaume · Accepted Answer · 2019-05-28T12:25:43

The output should be the sum:

System.out.println(kadanesum);

And not the message you wrote:

System.out.println("\tKadane Sum = " + kadanesum);

And as Rahul pointed out, you also need to remove the other messages such as:

System.out.println("Enter the array elements separated by space");

Maximum sum of sub-array using Kadane's Algorithm in Java

1 Answers