Kadane’s Algorithm

 

public class kadane {
    public static void main(String args[])
    {
            System.out.println("Kadane Algorithm");
           
            int A[]={-2, -3, 4, -1, -2, 1, 5, -3};
            int max , max_final , i;
            max=max_final=0;
            int size=A.length;
            for(i=0;i<size;i++)
            {
                max=max+A[i];
                if(max < 0)
                    max=0;
               
                if(max_final<max)
                    max_final=max;
                           
            }
            System.out.println("Maximum sum : "+max_final);
    }
}

Output:

Maximum sum : 7

Some of the interview questions asked recently

 

1. Given a binary tree & a sum value. Find the two nodes in a binary tree whose sum is equal to the given sum.

2. Print all the permutations of a string.

3. Detect and remove the loop in linked list.

4. Given a binary tree , find the maximum rooted subtree (whose sum of its child is greater than other sub trees).

5. Difference between abstract class & packages in Java.

6. Convert Binary Search Tree to Sorted Doubly linked list.

7. Maximum circular subarry sum.

8. Given 3 numbers. Find the lease valid date formed by those numbers.

eg: 1,2 ,3. Output should be : 3/2/1. Note: should take care of cases like valid month & date & leap year.

9. Given binary tree . Print the sum of all the leaf nodes.

10. Given two sorted arrays , ‘A’ of size m and ‘B’ of size n+m. Array B will contain numbers in n positions and ‘m’ empty positions. Merget two Arrays. Note: Should not use extra memory.