Index

1. Linked List implementation in Java
2. Other Linked List Problems
     a. Reverse a Linked List
     b. Get Nth element from the end of a linked list.
     c. Check if a linked list is a palindrome  
3. Queue implementation in Java using Linked List.
4. Stack implementation in Java using Linked List.
5. Binary Search Tree implementation in Java
6. Other Binary Tree Problems
    a. Compare two binary trees
    b. Convert a binary tree to a doubly linked list
    c. Build binary tree from preorder traversal and inorder traversal
    d. Build NL tree from preorder traversal
    e. Convert each level of a binary tree into a linked list
    f. Non recursive tree traversal using stack
    g. Descending order traversal of binary search tree
7. Hash Table implementation using separate chaining 
8. Other Problems
    a. Multiple Producer Consumer Problem
    b. Pattern Matching
    c. Find if a number is divisible by 3
    d. Calculate x^m in O(log m) time
    e. De duplicate array in O(n) time
    f. Reverse factorial
   g. Shuffle a pack of 52 cards
   h. Find the intersection of 2 arrays
   i. Find duplicate elements in a array
  j. Set bit count

Largest Sum contiguous subarray

 Problem . 

 An array can contains negative and positive numbers. You have to find the sub-array where the sum of all numbers in the sub array is maximum.

In the above example the largest sum in a sub-array is 14.



Solution.


The crux of the logic is the fact that, as you read from left, if a subset sums up to a -ve number, you can discard it. It won't be able to contribute anything to the numbers following it.

You need to keep track of two sums. First, the largest sum found so far from beginning (maxSoFar ) and another sum  for the sub-array currently being considered (currentSubArrayMax ). Whenever
sum of the current sub-array is more than the global max assign maxSoFar = currentSubArrayMax.


public static int maxSumSubArray (int[] numbers)
{


int currentSubArrayMax = 0;
int maxSoFar = 0;

for (int i = 0; i < numbers.length; i++)
{
currentSubArrayMax += numbers[i];



//if a subset adds up to a -ve number, discard it
if (currentSubArrayMax  < 0)
currentSubArrayMax = 0;

//set the new maximum
if (maxSoFar < currentSubArrayMax)
maxSoFar = currentSubArrayMax;
}

return maxSoFar ;
}