[알고리즘] 최대 누적 과 문제

3136 단어
1. 하위 배열 의 최대 누적 과 문제
제목:
하위 배열 의 최대 누적 합 을 되 돌려 주 는 배열 을 지정 합 니 다.
예 를 들 어 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;
	}

좋은 웹페이지 즐겨찾기