One Dimensional Kadane Implementation for Largest Sum Contiguous Subarray

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

public class LargestSumContiguousSubarray {

   
    public static void main(String[] args) throws IOException {
       
        BufferedReader input=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the size of input integer array: ");
        int input_size=input.read();
       
        // take a integer array to store all input upto input_size
        int input_array[] = new int[input_size];
        for(int count=0;count<input_array.length;count++)
        {
            input_array[count]=input.read();
        }
       
        // function call to calculate largest sum contiguous subarray
       
        int largestSumContiguousSum=findLargestSumContiguousSubarray(input_array,input_size);
        System.out.println(largestSumContiguousSum);

    }

   
    // function to calculate largest sum contiguous subarray using Kadane's one dimentional algorithm
    private static int findLargestSumContiguousSubarray(int[] input_array,
            int input_size) {
       
        int final_maxSum=0,current_maxSum=0;
        boolean allNegative=true;
        // to handle the case when all numbers are negative
       
        for(int count=0;count<input_size;count++)
        {
            if(!(input_array[count]<0))
            {
                allNegative=false;
            }
           
            if(final_maxSum<input_array[count])
            {
                final_maxSum=input_array[count];
            }
        }
        // if all numbers are negative then return the maximum of them
        if(allNegative){
            return final_maxSum;
        }
       
        // actual implementation of kadane's algorithm
        for(int count=0;count<input_size;count++)
        {
            current_maxSum=current_maxSum+input_array[count];
            if(current_maxSum<0)
            {
                current_maxSum=0;
            }
            else
            {
                if(final_maxSum<current_maxSum)
                {
                    final_maxSum=current_maxSum;
                }
            }
        }
       
        return final_maxSum;
    }

}

KMP Search

/* JAVA IMPLEMENTATION */

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

public class KMPSearch {

    /**
     * @param args
     */
public static void main(String[] args) throws IOException {
       
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text= new String(br.readLine());
        String pattern=new String(br.readLine());
        kmpSearch(text,pattern);

    }

    private static void kmpSearch(String text, String pattern) {
       
        int text_index=0,pattern_index=0;
        int text_length=text.length();
        int pattern_length=pattern.length();
        int lpt[]=new int[pattern_length+1];
        computeLongestPrefixTable(pattern,pattern_length,lpt);
        while(text_index<text_length)
        {
            if(text.charAt(text_index)==pattern.charAt(pattern_index))
            {
                text_index++;
                pattern_index++;
            }
            else if(text.charAt(text_index)!=pattern.charAt(pattern_index))
            {
                if(pattern_index!=0)
                {
                    pattern_index=lpt[pattern_index-1];
                }
                else
                {
                    text_index++;
                }
            }
            if(pattern_index==pattern_length)
            {
                System.out.println("PATTERN MATCH AT "+(text_index-pattern_index));
                pattern_index=lpt[pattern_index-1];
            }
           
        }
       
    }

    // computing pattern table for prefix and suffix matching
    private static void computeLongestPrefixTable(String pattern,
            int pattern_length, int[] lpt) {
       
        int length=0;
        int index=0;
        lpt[index++]=0; // first element is always  zero
       
        while(index<pattern_length)
        {
            if(pattern.charAt(length)==pattern.charAt(index))
            {
                length++;
                lpt[index]=length;
                index++;
            }
            else
            {
                if(length!=0)
                {
                    length=lpt[length-1];
                }
                else
                {
                    lpt[index++]=0;
                }
            }
        }
    }


}