[알고리즘/자바스크립트] 연속하는 숫자의 합 중 가장 큰 값 구하기 (Maximum subarray sum)

-해당 문제는 codewars사이트의 level5 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

 

 

[문제] 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.

---

[해석] 배열에서 연속하는 숫자들의 합 중에서 가장 큰 값을 구하는 문제이다.

위 예시 코드에서는 4 + (-1) + 2 + 1이 6으로 가장 크기 때문에 6을 return해야한다.

 

만약에 배열의 모든 숫자가 양수로만 되어있다면 모든 숫자를 다 더한 값을 return하면 된다.

만약 배열의 모든 숫자가 음수거나 빈 배열이라면 0을 return한다.

 

---

 

var maxSequence = function(arr){
	if (arr.length === 0 || arr.every((v) => v < 0)) {
		return 0;
	}

	var newArr = [];
	var sum = arr.reduce(function(ac, cv, i, arr) {
		if(ac < 0) {
			ac = 0;
		}
		newArr.push(ac);
		return ac + cv;
	}, 0);
	newArr.push(sum)
	return Math.max(...newArr)
}

일단 제일 처음 생각해 낸 코드는 위와 같다.

 

1. 먼저 배열의 길이가 0이거나 배열의 모든 요소가 0보다 작은 음수인 경우 0을 return해준다.

arr.every((v) => v <0)으로 배열의 모든 요소가 음수인지 아닌지 판별하였는데,

every()는 배열 요소들을 돌면서 모든 요소가 지정한 조건에 맞으면 true를 return하고 

하나라도 조건에 맞지 않으면 false를 return하는 함수이다.

 

사실 이걸 쓰면서도 좀 찝찝했던 것이 밑에서도 반복 돌려서 최대값 구하고 할텐데

이 조건식에서 이렇게 반복문으로 판별을 해버리면 뭐랄까.. 쓸데없이 2번 반복하는 느낌..(?)

그래서 이 부분은 밑에 다른 코드를 보면 삭제되어있다.

 

2. 그 다음에 newArr라는 빈 배열을 만든다.

 

3. arr에 reduce() 함수를 사용할 것이다. 변수 ac(accumulator)에 cv(current value)를 누적해서 더해준다.

다만, ac의 값이 0보다 작아지면 0으로 초기화시켜준다.

왜냐면 우리는 연속하는 숫자의 합 중 가장 큰 값을 구해야하기 때문이다.

예를 들면 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 배열을 넣고 값을 구한다고 했을 때,

앞에서부터 차례로 더하면 (-2) + 1 + (-3)을 더하면 -4가 된다.

이 값을 0으로 초기화해주지 않으면 -4에 그대로 4를 더해 누적값이 작아져버린다.

 

4. 누적되는 값을 newArr에 계속 push해서 넣어준다.

5. reduce함수가 끝나고 마지막으로 return되는 값도 newArr에 push해준다.

6. newArr에 들어있는 값 중에서 가장 큰 값을 최종적으로 return한다.

 

---

 

위 코드도 문제없이 실행되지만 좀 더 간단하게 고쳐보고 싶었다.

특히 음수판별을 every조건식으로 하고 싶지가 않았고,

새로운 배열을 만들지 않고 더 쉽게 바꾸고 싶어서 아래처럼 고쳐보았다.

var maxSequence = function(arr){
	var max = 0;
	var sum = arr.reduce(function(ac, cv) {
		if(ac < 0) {
			ac = 0;
		}
		if(ac > max) {
			max = ac;
		}
		return ac + cv;
	}, 0);
	return Math.max(sum, max);
}

0. 빈 배열인지, 음수로만 이루어진 배열인지 판별하는 조건문을 삭제했다.

(이유는 해당 조건인 경우에 아래 과정을 거치면 자연스럽게 0이 return되기 때문이다.)

1. max라는 변수에 0을 할당해둔다.

2. ac가 0보다 작아지면 ac를 무조건 0을 할당하고, ac가 max보다 크면 max에 ac를 할당한다.

3. 그리고 reduce함수가 종료된 후 최종 더한 값인 sum과 max 중 더 큰 값을 return한다.

 

이 경우에 배열의 모든 요소가 음수라면 max의 값은 바뀌지 않고 계속 0일거고

마지막에 sum과 max를 비교하여 더 큰 값인 0을 return할테니

every함수를 쓰지 않아도 자연히 음수일 땐 0이 return된다.

 

---

 

똑같은 코드를 reduce()가 아닌 forEach() 함수로 적용해보았다.

var maxSequence = function(arr){
    var max = 0, sum = 0;
    arr.forEach(function(num) {
        sum += num;
        if (sum < 0) {
            sum = 0;
        }
        if (sum > max) {
            max = sum;
        }
    });
    return Math.max(sum, max);
}

이 코드가 위 코드보다 더 이해하기 쉬운 것 같다.

 

---

 

마지막으로 알고리즘을 해결하고 다른 사람들 풀이를 쭉 보다가

나랑 비슷한 매커니즘의 방법이지만 다른 방식으로 푼 풀이가 있어서 아래 적어보았다.

var maxSequence = function(arr){
	var max = 0;
	var cur = 0;
	arr.forEach(function(i){
		cur = Math.max(0, cur + i);
		max = Math.max(max, cur);
	});
	return max;
}

cur라는 변수에 0과 배열의 값을 누적해서 더한 값을 비교하여 더 큰 값을 담는다.

즉, 값이 음수가 되면 0을 return한다. 

내가 if(av < 0) { av = 0; }라고 적은 것과 같은 문장이다.

그리고 max와 cur를 비교해서 더 큰 값을 max에 담는다.