max_sum.java

/**
 * Created by xynophon on 15.1.13.
 */
import java.util.Random;
public class max_sum {
    public double max(double i, double j){
        if(i == j)return i;
        return (i<j)?j:i;
    }

    // O(n^2)
    public double max_sum(double[] arr){
        double ret = -987654321;
        for(int i = 0; i < arr.length; i++){
            double sum = 0;
            for(int j = i; j < arr.length; j++){
                sum += arr[j];
                ret = max(ret, sum);
            }
        }
        return ret;
    }

    // O(lgn)
    public double fast_max_sum(double[] arr, int lo, int hi){
        if(lo==hi)
            return arr[lo];
        int mid = (lo+hi)/2;
        double sum = 0;
        double left = -987654321;
        double right = -987654321;
        for(int i = mid; i >= lo; --i){
            sum += arr[i];
            left = max(left, sum);
        }

        right = -987654321;
        sum = 0;
        for(int j = mid+1; j <= hi; ++j){
            sum += arr[j];
            right = max(right, sum);
        }

        double single = max(fast_max_sum(arr, lo, mid), fast_max_sum(arr, mid+1, hi));
        return max(left+right, single);
    }

    // O(n)
    public double fastest_max_sum(double[] arr){
        double ret = -987654321;
        double psum = 0;
        for(int i = 0; i < arr.length; i++){
            psum = max(0, psum)+arr[i];
            ret = max(ret, psum);
        }
        return ret;
    }

    public static void main(String args[]){
        max_sum ms = new max_sum();
        Random rn = new Random();
        double[] arr  = {5, 2, -5, 4, -5, -6, -7, -8, -9};
        for(int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("max_sum: "+ms.max_sum(arr));
        System.out.println("fast_max_sum: "+ms.fast_max_sum(arr, 0, arr.length-1));
        System.out.println("fastest_max_sum: "+ms.fastest_max_sum(arr));
    }
}