CodeWars 5kyu Maximum subarray sum

2019년에 Hexo 블로그에 쓴 글을 옮겨 왔습니다. 당시 이해를 그대로 두었습니다.

CodeWars 5kyu. Maximum subarray sum

Return maximum sum of subarrays

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.

Requirement

Should return maximum sum of any subarrays including empty list.
Return 0 when all of list’s element is negative numbers.

Solution

I used Dynamic Programming - Bottom up approach to solve this problem. Because I learned on some online lectures about Dynamic Programming recently.

First I catched that all the start and end element in subarray is positive numbers. So I decided to put all positive numbers’ index in positive_index list.
Make a 2 dementional array, sum[][] to keep the sum of subarrays.
Drew the recurrance Induction of this problem.
- Basis
  - sum[i][i] = arr[positive_index[i]]
  - sum[i][i+1] = arr[positive_index[i]] to arr[positive_index[j]] (i < positive_index.length - 1)
- Inductive Step
  - sum[i][j] = sum[i][j-1] + sum[j-1][j] - arr[positive_index[j-1]]

javaScript Solution

Submit

var maxSequence = function(arr){
  var positive_index = []
 
  arr.filter(function positive_check(element, index){
    if(element>0){
      positive_index.push(index);
    }
  })
  
  if (positive_index.length == 0) return 0;
  
  var sum = Array(positive_index.length).fill(null).map(() => Array(positive_index.length));
  var max = Number.MIN_SAFE_INTEGER;

  for(var i=0; i<positive_index.length; i++){
    sum[i][i] = arr[positive_index[i]];
    if(max < sum[i][i]){
        max = sum[i][i];
    }
    if(i+1<positive_index.length){
      sum[i][i+1] = arr.slice(positive_index[i], positive_index[i+1]+1).reduce((a,b)=>a+b);
      if(max < sum[i][i+1]){
        max = sum[i][i+1];
      }
    }
  }
  
  for(var i=0; i< positive_index.length; i++){
    for(var j=i+2; j< positive_index.length; j++){
      sum[i][j] = sum[i][j-1] + sum[j-1][j] - arr[positive_index[j-1]];
      if(max < sum[i][j]){
        max = sum[i][j];
      }
    }
  }
  return max;
}