[알고리즘] 최대 누적 과 문제
제목:
하위 배열 의 최대 누적 합 을 되 돌려 주 는 배열 을 지정 합 니 다.
예 를 들 어 arr = [1, - 2, 3, 5, - 2, 6, - 1], 모든 하위 배열 에서 [3, 5, - 2, 6] 은 가장 큰 것 과 12, return 12 를 누적 할 수 있다.
요청:
시간 복잡 도 는 O (N) 이 고 추가 공간 복잡 도 는 O (1) 이다.
생각:
만약 arr 에 정수 가 없다 면, 발생 하 는 최대 누적 과 반드시 배열 의 최대 값 입 니 다.
arr 에 정수 가 있 으 면 왼쪽 에서 오른쪽으로 arr 를 옮 겨 다 니 며 변수 cur 로 모든 단계 의 누적 과 정수 cur 가 증가 하고 마이너스 cur 로 옮 겨 다 니 며 감소 합 니 다.cur < 0 시 현재 부분 을 버 리 고 cur = 0 을 명령 하면 다음 숫자 부터 누적 되 는 것 을 표시 합 니 다.cur > = 0 시, 매번 의 누적 은 최대 의 누적 과 일 수 있 으 므 로, 다른 변수 max 로 cur 가 나타 난 최대 치 를 추적 합 니 다.
public static int maxSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i != arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}二、子矩阵的最大累计和问题
题目：
给定一个矩阵，其中的值有正、有负、有0。返回子矩阵的最大累计和。
核心思路：
如果一个矩阵一共有K行且限定必须含有K行元素的情况下，只要把矩阵中每一行的K个元素累加生成一个累加数组，然后求出这个数组的最大累加和，这个最大累加和就是必须含有K行元素的子矩阵中的最大累加和。
public static int maxSum(int[][] m) {if (m == null || m.length == 0 || m[0].length == 0) {return 0;}int max = Integer.MIN_VALUE;int cur = 0;int[] s = null;for (int i = 0; i != m.length; i++) {s = new int[m[0].length];for (int j = i; j != m.length; j++) {cur = 0;for (int k = 0; k != s.length; k++) {s[k] += m[j][k];cur += s[k];max = Math.max(max, cur);cur = cur < 0 ? 0 : cur;}}}return max;}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
