javaScript 연속 하위 배열 의 최대 합

3784 단어 알고리즘
하나의 정형 배열 을 입력 하 십시오. 하위 배열 은 이 배열 의 연속 적 인 하나 또는 여러 개의 정수 로 구 성 된 배열 입 니 다.모든 하위 배열 의 합 의 최대 치 를 구하 십시오.시간 복잡 도 를 O (n) 로 요구 합 니 다.예 를 들 어 입력 배열 은 [1, - 3, 9, 10, - 2, 3, - 6, 5] 이다.가장 큰 하위 그룹 과 [9, 10, - 2, 3] 이 므 로 이 하위 그룹 과 20 으로 출력 합 니 다.
function contMax(array) {
	if (array.length == 0)
		return 0
	var sum = array[0] //      
	var maxSum = array[0] //        
	for (var i = 1; i < array.length; i++) {
		sum = Math.max(sum + array[i], array[i]);
		maxSum = Math.max(sum, maxSum)
	}
	return maxSum
}

console.log(contMax([1, -3, 9, 10, -2, 3, -6, 5])) //20

좋은 웹페이지 즐겨찾기