Problem of the Day
A new programming or logic puzzle every Mon-Fri

Given an array of integers find the largest consecutive sum of 3 integers. In the array [1,5,8,3,2,7,4], the largest sum of 3 consecutive is 5+8+3. When you find the largest sum print out the 3 integers. Can you solve this in O(n)?

Comments:

• Anon - 10 years, 1 month ago

  Java; Sorry if this is not O(n). I'm still new to big O notation.

    public int largestSum (int[] array) {
      Arrays.sort(array);
      int largest = array[array.length - 1];
      int nextLargest = array[array.length - 2];
      int thirdLargest = array[array.length - 3];
      return largest + nextLargest + thirdLargest;
    }
  

  reply permalink

• Anonymous - 10 years, 1 month ago

  Sorting the array changes the order so you can not ensure the three largest ints were consecutive before the sort.

  An example: {0,1,0,0,3,0,0,5} should return 5 but your function would return 9.

  Your implementation's runtime is bounded by Arrays.sort() run time which is O(n log n).

  reply permalink

• Anonymous - 10 years, 1 month ago

  Javascript - how's this?

  var largest = function(array) {
    array = array || [];
  
    var largestTotal = 0;
    var results = [];
  
    if(array.length < 4) {
      return array;
    }
  
    for(var i = 0; i < array.length; i++) {
      var arr = array.slice().splice(i, 3);
      var total = arr.reduce(function(a, b) {
          return a + b;
      });
  
      if(total > largestTotal) {
          largestTotal = total;
          results = arr;
      }
    }
  
    return results;
  };
  

  reply permalink

• Anonymous - 10 years, 1 month ago

  def max3sum(lst):
      return max(map(sum, zip(lst, lst[1:], lst[2:])))
  
  print(max3sum([1,5,8,3,2,7,4]))
  

  O(n), python, beautifully simple

  reply permalink

• asheehan - 10 years, 1 month ago

  in ruby:

  def max_sum(input)
      threes = Array.new
      input.each_with_index { |x, i|
          if i > (input.length - 3)
              break
          end
          threes << [x, input[i+1], input[i+2]].inject(0, &:+)
      }
      p input.slice(threes.index(threes.max), 3)
  end
  
  input = [1,5,8,4,2,7,4]
  max_sum(input)
  

  not the cleanest, but it works and is pretty close to O(n)

  reply permalink

• asheehan - 10 years, 1 month ago

  rewrote this a little to be O(n)

  def max_sum(input)
    max = 0
    max_index = 0
    input.each_with_index do |x, i|
      if i > (input.length - 3)
        break
      end
      current_value = [x, input[i+1], input[i+2]].inject(0, &:+)
      if current_value > max
        max = current_value
        max_index = i
      end
    end
    return input.slice((max_index), 3)
  end
  
  input = [1,5,8,4,9,7,4]
  p max_sum(input)
  

  reply permalink