largestContinuousSum

largestContinuousSum

public static LinkedList<Integer> largestContinuousSum(int[] array) {

	if (array.length == 0) return null;
	
	LinkedList<Integer> current_path, max_path;
	int current_sum, max_sum;
	
	max_path = current_path = new LinkedList<Integer>();
	current_sum = max_sum = Integer.MIN_VALUE;
	
	for (int i : array) {
		if (current_sum < 0 && current_sum < i) {
			current_path = new LinkedList<Integer>();
			current_path.add(i);
			current_sum = i; 
		} else if (current_sum + i >= current_sum) {
			current_path.add(i);
			current_sum += i;
		} else {
			if (max_sum < current_sum) {
				max_path = current_path;
				max_sum = current_sum;
				current_path = new LinkedList<Integer>();
				current_sum = 0;
			}
		}
	}
	
	if (current_sum > max_sum) {
		max_path = current_path;
	}
	
	return max_path;
}