Dynamic Programming - Longest Palindrome in a sequence

 package com.imaginea.dynamicprogramming;  
 import java.util.HashMap;  
 import java.util.Map;  
 /*  
  * Dynamic Programming implementation to get longest Palindrome in string sequence  
  * In order to solve a given problem, using a dynamic programming approach, we need to solve different parts of the problem (subproblems),   
  * then combine the solutions of the subproblems to reach an overall solution  
  * It is applicable to problems exhibiting the properties of 1. Optimal Substructure and 2. Overlapping Subproblem  
  * 1. Optimal Substructure: If optimal solution can be constructed efficiently from optimal solution of its subproblem.  
  * 2. Overlapping Subproblem: if the problem can be broken down into subproblem which are reused several times rather than to generate new subproblem.  
  *   
  * LP(i,j)     =1                    if i==j  
  *                =1                    if j=i+1 and x[i]!=x[j]  
  *                =2                     if j=i+1 and x[i]==x[j]  
  *                =LP(i+1, j-1)+2  
  *                =max(LP(i+1,j),LP(i,j-1))  
  */  

 public class LongestPalindromeSequence {  
      static Map<String, Integer> computedValues = new HashMap<String, Integer>();  
      public static void main(String[] args) {  
           int length = LP("BBABCBCAB");  
           System.out.println("Paliandrome Length::"+length);  
      }  
      private static int LP(String str){  
           if(computedValues.get(str)!= null){  
                return computedValues.get(str);  
           }  
           if(str.length()>0){  
                int i=0;  
                int j=str.length()-1;  
                if(i==j){  
                     return 1;  
                }else if(j == (i+1)){  
                     if(str.charAt(i)==str.charAt(j)){  
                          return 2;  
                     }else{  
                          return 1;  
                     }  
                }else if(str.charAt(i)==str.charAt(j)){  
                     int result = LP(str.substring(i+1, j))+2;  
                     computedValues.put(str,result);  
                     return result;  
                }else{  
                     int result = max(LP(str.substring(i+1, j+1)),LP(str.substring(i, j)));  
                     computedValues.put(str, result);  
                     return result;  
                }  
           }else{  
                System.out.println("Invalid String");  
                return -1;  
           }  
      }  
      private static int max(int n, int m){  
           if(n>m)  
                return n;  
           else  
                return m;  
      }  
 }  

Quick Sort Java Code

 /*  
  * QuickSort  
  * Best case performance             O(n log(n))  
  * Average case performance          O(n log(n))  
  * Worst case performance            O(n^2)  
  * Worst case space complexity       O(log(n))  
  */  
 public class QuickSortExample {  
      public static void main(String[] args) {  
           int[] array= {4,2,3,5,6,9};  
           recursiveQuickSort(array, 0, array.length-1);  
           for(int i:array){  
                System.out.println(i+" ");  
           }  
      }  
      private static void recursiveQuickSort(int[] array, int startIdx, int endIdx){  
           int idx = partition(array, startIdx, endIdx);  
           if(startIdx < idx-1){  
                recursiveQuickSort(array, startIdx, (idx-1));  
           }  
           if(endIdx > idx){  
                recursiveQuickSort(array, idx, endIdx);  
           }  
      }  
      private static int partition(int[] array, int leftPtr, int rightPtr){  
           int pivot = array[leftPtr];  
           while(leftPtr <= rightPtr){  
                while(array[leftPtr] < pivot){  
                     leftPtr++;  
                }  
                while(array[rightPtr]>pivot){  
                     rightPtr--;  
                }  
                if(leftPtr<=rightPtr){  
                     int tmp = array[leftPtr];  
                     array[leftPtr] = array[rightPtr];  
                     array[rightPtr] = tmp;  
                     leftPtr++;  
                     rightPtr--;  
                }  
           }  
           return leftPtr;  
      }  
 }  

Merge Sort Java Code

 package com.imaginea.ds.practice;  
 /*  
  *MergeSort  
  *     Worst case performance     O(n log n)  
  *     Best case performance     O(n log n) typical,     O(n) natural variant  
  *     Average case performance     O(n log n)  
  *     Worst case space complexity     O(n) auxiliary  
  */  
 public class MergeSortExample {  
      static int[] arr = {45,23,11,89,77,98,4,28,65,43};  
      public static void main(String[] args) {  
           doMergeSort(0, arr.length-1);  
           for(int num:arr){  
                System.out.print(num+" ");  
           }  
      }  
      private static void doMergeSort(int lowerIdx, int higherIdx){  
           if(lowerIdx < higherIdx){  
                int middleIdx = lowerIdx + (higherIdx - lowerIdx)/2;  
                doMergeSort(lowerIdx, middleIdx);  
                doMergeSort(middleIdx+1, higherIdx);  
                mergeArray(lowerIdx, middleIdx, higherIdx);  
           }  
      }  
      private static void mergeArray(int lowerIdx, int middleIdx, int higherIdx){  
           int i=lowerIdx;       
           int j=middleIdx+1;  
           int k=lowerIdx;  
           int[] tmpArr= new int[higherIdx+1];  
           for(int idx=lowerIdx;idx<=higherIdx; idx++){  
                tmpArr[idx]=arr[idx];  
           }  
           while(i<=middleIdx && j<=higherIdx){  
                if(tmpArr[i] <= tmpArr[j]){  
                     arr[k]=tmpArr[i];  
                     i++;  
                }else{  
                     arr[k]=tmpArr[j];  
                     j++;  
                }  
                k++;  
           }  
           while(i <= middleIdx){  
                arr[k]=tmpArr[i];  
                k++;  
                i++;  
           }  
      }  
 }  

Sum of 1 to 10000 using ForkJoinPool framework

 import java.util.ArrayList;  
 import java.util.Arrays;  
 import java.util.List;  
 import java.util.concurrent.RecursiveTask;  
 public class ArraySplit extends RecursiveTask<Long>{  
      /**  
       *   
       */  
      private static final long serialVersionUID = 1L;  
      private Integer[] list;  
      public ArraySplit() {}  
      List<ArraySplit> taskList = new ArrayList<ArraySplit>();  
      public ArraySplit(Integer[] list) {  
           this.list = list;  
      }  
      @Override  
      protected Long compute() {  
           int sum = 0;  
           if(list.length <= 1000){  
                for(int i:list){  
                     sum += i;  
                }  
           }else{  
                int midpoint = list.length / 2;  
                Integer[] l1 = Arrays.copyOfRange(list, 0, midpoint);   
                Integer[] l2 = Arrays.copyOfRange(list, midpoint, list.length);  
                ArraySplit st1 = new ArraySplit(l1);      st1.fork();  
                ArraySplit st2 = new ArraySplit(l2);     st2.fork();  
                taskList.add(st1);  
                taskList.add(st2);  
           }  
           return addResultFromSubTask(sum, taskList);  
      }  
      private Long addResultFromSubTask(int sum, List<ArraySplit> taskList){  
           int result = 0;  
           for(ArraySplit splitTask: taskList){  
                result += splitTask.join();  
           }  
           return (long) (result + sum);  
      }  
 }  

Above code divides the long array into multiple sub-array. Sum of sub-array value is combined with other sub-array sum value and is returned to the calling method. Sum of sub-arrays is handled by different thread results in faster calculation.