Maximum subarray sum ( 5 kyu )

Maximum subarray sum ( 5 kyu )

문제

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.

배열에서 연속된 원소의 합이 최대일 때를 구하는 문제

풀이

var maxSequence = function(arr){
  let max = 0, sum = 0, j;
  for ( let i = 0; i < arr.length; i++ ) {
    sum = 0;
    j = i;
    while ( sum <= max ) {
      sum += arr[j]
      if ( sum > max ) {
        max = sum;
      }
      j++;
    }
  }
  return max
}

for, while로 a에 b의 원소들이 없을때까지 반복해서 리턴

다른 사람의 풀이

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

포문 하나로 해결.

이게 더 좋은 코드