Maximum Subarray Problem

MaximumSubarray.java

import java.util.Arrays;

public class MaximumSubarray {

    private int sum(int input[]) {
        int s = 0;
        for (int i = 0; i < input.length; i++) {
            s += input[i];
        }
        return s;
    }

    /*
     * @param input - an array with positive and negative integers
     * @return - maximum subarray sum
    */
    public int maximumSubarraSumQuadratic(int input[]) {
        int max = 0;
        for (int i = 0; i < input.length; i++) {
            for (int j = i + 1; j < input.length; j++) {

                int s = sum(Arrays.copyOfRange(input, i, j + 1));
                max = Math.max(s, max);
            }
        }
        return max;
    }

    public int[] maximumSubarraSumArrayQuadratic(int input[]) {
        int max = 0;
        int maxArray[] = null;
        for (int i = 0; i < input.length; i++) {
            for (int j = i + 1; j < input.length; j++) {

                int s = sum(Arrays.copyOfRange(input, i, j + 1));
                if (s > max) {
                    maxArray = Arrays.copyOfRange(input, i, j + 1);
                    max = s;
                }
            }
        }
        return maxArray;
    }

    private static void print(int input[]) {

        if (null == input || input.length == 0) {
            System.out.println("null Or Empry");
            return;
        }

        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + " ");
        }
        System.out.println();
    }


    public int maximumSubarraSumLinearTime(int input[]) {
        int runningSum = 0, maxSum = 0;
        
        for(int i =0; i< input.length; i++) {
            int currentElement = input[i];
            
            if((currentElement+runningSum) >= 0)
                runningSum = currentElement+runningSum;
            else
                runningSum = 0;
                
            maxSum = Math.max(runningSum, maxSum);    
        }
        
        return maxSum;
    }
    
    public static void main(String args[]) {

        MaximumSubarray maximumSubarray = new MaximumSubarray();

        // System.out.println(maximumSubarray.maximumSubarrayLength(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));

        System.out.println(maximumSubarray.maximumSubarraSumQuadratic(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));

        print(maximumSubarray.maximumSubarraSumArrayQuadratic(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }

}