Skip to content

Instantly share code, notes, and snippets.

@alexandervasyuk

alexandervasyuk/largestContinuousSum

Last active August 29, 2015 14:07
Download ZIP

Revisions

  1. alexandervasyuk revised this gist Oct 3, 2014. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions largestContinuousSum
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,7 @@
    public static LinkedList<Integer> largestContinuousSum(int[] array) {

    if (array.length == 0) return null;

    LinkedList<Integer> current_path, max_path;
    int current_sum, max_sum;

  2. alexandervasyuk created this gist Oct 3, 2014.
    31 changes: 31 additions & 0 deletions largestContinuousSum
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,31 @@
    public static LinkedList<Integer> largestContinuousSum(int[] array) {
    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;
    }