CareerCup

using kobane algorithm is best for time complexity

public class MaxSubArraySum {
	public static void main(String[] args){	
		int[] source = {1, 2, 2, 3, 5, 8, 9};
		int[] source1 = {1, -3, 2, -5, 7, 6, -1, -4, 11, -23};
		int[] source2 = {-52,-9,-5,-1,-13};
		
		MaxSubArraySum mss = new MaxSubArraySum();
		System.out.println(mss.MaxSubArraySum_BruteForce1(source));
		System.out.println(mss.MaxSubArraySum_BruteForce1(source1));
		System.out.println(mss.MaxSubArraySum_BruteForce1(source2));

		System.out.println(mss.MaxSubArraySum_BruteForce2(source));
		System.out.println(mss.MaxSubArraySum_BruteForce2(source1));
		System.out.println(mss.MaxSubArraySum_BruteForce2(source2));
		
		System.out.println(mss.MaxSubArraySum_DivideConquer(source, source.length));
		System.out.println(mss.MaxSubArraySum_DivideConquer(source1, source1.length));
		System.out.println(mss.MaxSubArraySum_DivideConquer(source2, source2.length));
		
		System.out.println(mss.MaxSubArraySum_Kobane(source));
		System.out.println(mss.MaxSubArraySum_Kobane(source1));
		System.out.println(mss.MaxSubArraySum_Kobane(source2));
	}
	
	/**
	 * 0(n power 3)
	 * brute force
	 * 
	 * @param input
	 * @return
	 */
	private int MaxSubArraySum_BruteForce1(int[] input){
		//validation
		if( input.length < 1 ) return 0;
		
		int ans = Integer.MIN_VALUE;	
		int length = input.length;
		
		for (int sub_array_size = 1; sub_array_size <= length; sub_array_size++) // O(n)
		{
			for (int start_index = 0; start_index < length; start_index++) // O(n)
			{
				if (start_index + sub_array_size > length) // Subarray exceeds
					break;										// array bounds

				int sum = 0;
				for (int i = start_index; i < (start_index + sub_array_size); i++) {
					sum += input[i]; // O(n)
				}
			
				ans = Math.max(ans, sum);
			}
		}
		
		return ans;
	}
	
	/**
	 * o(nlogn)
	 * 
	 * @param input
	 * @param length
	 * @return
	 */
	private int MaxSubArraySum_DivideConquer(int[] input, int length){
		if (length == 1) {
			return input[0];
		}
		int mid = length / 2;
		
		int[] leftArr = new int[mid];
		int[] rightArr = new int[length - mid];
		for(int i = 0; i < mid; i++ ){
			leftArr[i] = input[i];
		}
		int count = 0;
		for(int i = mid; i < length; i++ ){
			rightArr[count] = input[i];
			count++;
		}
		
		int left_MSS = MaxSubArraySum_DivideConquer(leftArr, mid);
		int right_MSS = MaxSubArraySum_DivideConquer(rightArr, length - mid);
		
		int leftsum = Integer.MIN_VALUE, rightsum = Integer.MIN_VALUE, sum = 0;
		for (int i = mid; i < length; i++) {
			sum += input[i];
			rightsum = Math.max(rightsum, sum);
		}
		sum = 0;
		for (int i = (mid - 1); i >= 0; i--) {
			sum += input[i];
			leftsum = Math.max(leftsum, sum);
		}
		int ans = Math.max(left_MSS, right_MSS);
		return Math.max(ans, leftsum + rightsum);
	}
	
	/**
	 * 0(n power 2)
	 * brute force
	 * 
	 * @param input
	 * @return
	 */
	private int MaxSubArraySum_BruteForce2(int[] input){
		//validation
		if( input.length < 1 ) return 0;
		
		int ans = Integer.MIN_VALUE;	
		int length = input.length;
		
		for (int start_index = 0; start_index < length; start_index++) // O(n)
		{
			int sum = 0;
			for (int sub_array_size = 1; sub_array_size <= length; sub_array_size++) // O(n)
			{
				if (start_index + sub_array_size > length) // Subarray exceeds
					break;		// array bounds
				
				sum += input[start_index + sub_array_size - 1]; //Last element of the new Subarray
				ans = Math.max(ans, sum);
			}
		}
		
		return ans;
	}
	/**
	 * o(n)
	 * Kobane algorithm
	 * 
	 * @param input
	 * @return
	 */
	private int MaxSubArraySum_Kobane(int[] input){
		//validation
		if( input.length < 1 ) return 0;

		//init
		int ans = input[0], sum = 0;
		
		//handle negative numbers
		for( int i = 0; i < input.length; i++ ){ 
			ans = Math.max(input[i], ans);
		}
		if( ans < 0 )
			return ans;
		
		ans = 0; //reset answer
		for( int i = 0; i < input.length; i++ ){ 
			if(sum+input[i] < 0) {
				sum = 0;
			}
			else{
				sum = sum+input[i];
			}
			ans = Math.max(ans, sum);
		}
		
		return ans;
	}
}