The Maximum-Subarray Problem

What is meant by the maximum sub-array problem is that we want to find the non-empty, contiguous sub-array of an array whose values have the largest sum. Following is a divide & conquer solution implemented for it using Java language.

/**
 *
 * @author Rajind
 */
public class MaximumSubarrayProblem {
    public static int[] maxSubArray(int[] A) {
        int newsum = A[0];
        int max = A[0];

        int low = 0;
        int high = 0;

        for(int i=1;i<A.length;i++){ 
            if(newsum+A[i] > A[i]){
                high++;
            }else{
                low = i;
                high = i;
            }

            newsum = Math.max(newsum+A[i],A[i]);
            max= Math.max(max, newsum);
        }

        int[] arr = new int[3];
        arr[0] = max;
        arr[1] = low;
        arr[2] = high;
        return arr;
    }

    public static void main(String args[]){
        int[] arr = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
        int []array = maxSubArray(arr);
        System.out.println("max: "+array[0]);
        System.out.println("low: "+array[1]);
        System.out.println("high: "+array[2]);
    }
}

~Rajind Ruparathna

Reverse Words in a String

Reversing words in a string is a popular coding interview question. Here what is meant by reversing words in a string is something like this.

Input string:     “My name is rajind and i am a believer”
Output string:  “believer a am i and rajind is name My”

Doing this in-place without use additional space to store the string is the trick. Following is the java code to do that.

/**
 *
 * @author Rajind
 */
public class ReverseWordsString {

    public static char[] stringReverse(char[] arr, int start, int end){
        while(start < end){
            arr[start] = (char) (arr[start]^arr[end]);
            arr[end] = (char) (arr[start]^arr[end]);
            arr[start] = (char) (arr[start]^arr[end]);
            start++;
            end--;
        }
        return arr;
    }

    public static void main(String Args[]){
        /*char a = 'A';
        char b = 'B';
        a = (char) (a^b);
        b = (char) (a^b);
        a = (char) (a^b);

        System.out.println(a + "   "+ b);
        */

        char[] str = "My name is rajind and i am a believer".toCharArray();
        str = stringReverse(str, 0, str.length -1);

        int start = 0;
        for(int i=0; i < str.length; i++){
            if(str[i] == ' '){
                str = stringReverse(str, start, i-1);
                start = i + 1;
            }
        }

        str = stringReverse(str, start, str.length-1);
        System.out.println(str);
    }
}

~Rajind Ruparathna