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
– Rahul, Commented May 28, 2019 at 12:25

Guillaume · Accepted Answer · 2019-05-28 12:25:43Z

1

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");

answered May 28, 2019 at 12:25

Guillaume

14.7k3 gold badges46 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related