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;
                }
            }
        }
    }


}

Maximum size square sub-matrix with all 1s

Java Implementation:

import java.util.Scanner;

public class MaxSizeSquareSubMatrix {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        int rows=0,columns=0;
        rows=sc.nextInt();
        columns = sc.nextInt();
        int [][]array=new int[rows][columns];
        for(int index=0;index<rows;index++)
        {
            for(int subIndex=0;subIndex<columns;subIndex++)
            {
                array[index][subIndex]=sc.nextInt();
            }
        }
        printMaxSubArray(array,rows,columns);
        sc.close();
    }

    // funtion to print max square sub array in a matrix
    private static void printMaxSubArray(int[][] array, int rows, int columns) {
       
        int countArray[][]=new int[rows][columns];
        int max_countArray=0;
        int max_row=0,max_column=0,outer=0,inner=0;
       
        // set the first row of countArray
        for(int rowIndex=0;rowIndex<rows;rowIndex++)
        {
            countArray[rowIndex][0]=array[rowIndex][0];
        }
       
        // set the first column of countArray
        for(int colIndex=0;colIndex<columns;colIndex++)
        {
            countArray[0][colIndex]=array[0][colIndex];
        }
       
        // calculate the other values of countArray
        for(outer=1;outer<rows;outer++)
        {
            for(inner=1;inner<columns;inner++)
            {
                if(array[outer][inner]==1)
                {
                   
                    countArray[outer][inner]=min(countArray[outer][inner-1],
                            countArray[outer-1][inner],countArray[outer-1][inner-1])+1;
                }
                else
                {
                    countArray[outer][inner]=0;
                }
            }
        }
       
        // calculate the max value in countArray and its corresponding row and column index
        max_countArray=countArray[0][0];
        for(outer=0;outer<rows;outer++)
        {
            for(inner=0;inner<columns;inner++)
            {
                if(max_countArray<countArray[outer][inner])
                {
                    max_countArray=countArray[outer][inner];
                    max_row=outer;
                    max_column=inner;
                }
            }
        }
       
       
        // print the max sub array
       
        for(outer=max_row;outer>max_row-max_countArray;outer--)
        {
            for(inner=max_column;inner>max_column-max_countArray;inner--)
            {
                System.out.print(array[outer][inner] + " ");
            }
            System.out.println();
        }
    }

    // utility method to get minimum among three numbers
   
    private static int min(int a, int b, int c) {
        int min=a;
        if(min>b)
        {
            min=b;
        }
        if(min>c)
        {
            min=c;
        }
        return min;
    }

}