18 - Maximum subarray sum

Don't say so much, just coding...

Instruction

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

  maxSequence [-2, 1, -3, 4, -1, 2, 1, -5, 4]
  // should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

Ruby

Init

  def max_sequence(arr)
    #your code here
  end

Sample Testing

  Test.describe("Tests") do
  Test.assert_equals(max_sequence([]), 0)
  Test.assert_equals(max_sequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
  Test.assert_equals(max_sequence([11]), 11)
  Test.assert_equals(max_sequence([-32]), 0)
  Test.assert_equals(max_sequence([-2, 1, -7, 4, -10, 2, 1, 5, 4]), 12)
  end

Javascript

Init

  var maxSequence = function(arr){
    // ...
  }

Sample Testing

  describe( "maxSequence", function(){
    it("should work on an empty array",function(){
      Test.assertEquals(maxSequence([]), 0);
    });
    it("should work on the example",function(){
      Test.assertEquals(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6);
    });
  });

Thinking

想法(1): 透過迴圈從 1 ~ x 群來計算所有加總後，再來比較所有算出來的結果哪個是最大的。
想法(2): 需要考慮如果是空陣列，要塞 0 近陣列來跟 負數值 比最大的。

圖片來源：Unsplash Christin Hume

Hint & Reference

• Ruby
  • Ruby - apidock Each_cons
  • Ruby - apidock flatten
• JavaScript
  • JS - MDN Math.max()

Solution

Ruby

  # Solution 1
  def max_sequence(arr)
    (1..arr.size).map { |i| arr.each_cons(i).map(&:sum) }
                 .flatten
                 .push(0)
                 .max
  end

Javascript

  // Solution 1
  var maxSequence = function(arr){
    var maxSum = 0;
    var currentSum = 0;
    
    for (i = 0; i < arr.length; i++) {
      currentSum += arr[i];
      
      if (currentSum <= 0) 
        currentSum = 0
      maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
  }