프로 그래 밍 의 아름다움 연재 - 연속 서브 그룹 과 최대 값

문제.
정수 배열 을 정 하고 연속 적 인 하위 배열 과 최대 치 를 구 합 니 다. 예 를 들 어 1, 2, 3, 5, - 3, 2 의 최대 치 는 80, - 2, 3, 5, - 1, 2 의 최대 치 는 9 입 니 다.
분석 하 다.
에서 제시 한 알고리즘 은 매우 세련 되 지만 해석 은 비교적 복잡 하 다. 만약 에 '등급 별 조합' 의 측면 에서 이해 하면 매우 편리 하 다.
해법
두 개의 정수 변 수 를 설정 합 니 다: cur 와 sum 은 주어진 배열 에서 모든 요 소 를 순서대로 꺼 내 cur 에 추가 합 니 다. cur < 0 시 cur 를 초기 화 합 니 다.sum 기록 cur 에 나타 난 최대 값:

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

cur = cur < 0 ? array[ i ] : cur + array[ i ];

if (sum < cur) sum = cur;

return sum;

扩展问题二解法

如果要求得到最大和的连续子数组的起始位置，那么通过以上思路就更加容易写出代码：

int start1 = 0, start2 = 0, end = 0;

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

    if (cur < 0)

        cur = array[ i ];

        start2 = i;

    else cur += array[ i ];

    if (sum < cur)

        sum = cur;

        end = i;

        start1 = start2;

//   [start1, end]

이 예 에서 우 리 는 start 1, start 2 로 시작 위 치 를 기록 하고 end 로 종료 위 치 를 기록 합 니 다.start 2 는 '작업 변수' 에 해당 하 며, start 1 은 역대 최대 와 연속 하위 배열 의 시작 위 치 를 저장 합 니 다.
확장 문제 해법
만약 주어진 것 이 배열 이 앞 뒤 가 연 결 된 순환 배열 이 라면 어떻게 풀 어야 합 니까?먼저 함 수 를 설계 하고 주어진 배열 에서 from 에서 시작 하여 최대 to 로 끝 나 는 최대 와 연속 서브 배열 의 끝 위치, 사고 방향 은 앞의 해법 과 유사 합 니 다.

int MaxSum_Position(int[] array, int from, int to)

    int step = Math.Sign(to - from);

    int end = from;

    var cur = array[from];

    var sum = cur;

    for (int i = from + step; i != to + step; i += step)

        cur += array[ i ];

        if (sum < cur)

            sum = cur;

            end = i;

    return end;

이 함수 가 있 으 면 순환 배열 의 문 제 를 두 가지 상황 으로 나 눌 수 있 습 니 다. 하 나 는 연속 서브 배열 이 0 위 치 를 뛰 어 넘 었 고 하 나 는 뛰 어 넘 지 않 았 습 니 다.

int sum1 = MaxSum(array);//   0

int i = MaxSum_Position(array, 0, array.Length - 1);

int j = MaxSum_Position(array, array.Length - 1, 0);

int sum2 = 0;

if (i > j) j = i + 1;

for (int k = 0; k < array.Length; k++)

sum2 += array[ k ];

if (k == i) k = j - 1; //

return Math.Max(sum1, sum2);

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

프로 그래 밍 의 아름다움 - 2 진수 중 1 의 개 수 를 구하 다

질문 설명: 한 바이트 (8bit) 의 부호 없 는 정형 변수 에 대해 바 이 너 리 표시 중 '1' 의 개 수 를 구하 고 알고리즘 의 집행 효율 이 가능 한 한 높 아야 한다. 문제 풀이:...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

프로 그래 밍 의 아름다움 연재 - 연속 서브 그룹 과 최대 값

扩展问题二解法

좋은 웹페이지 즐겨찾기