최대 합이있는 부분 배열의 크기

난이도 쉽게
자주 묻는 질문 Coursera 그레이 오렌지 UHG 옵텀
배열 동적 프로그래밍조회수 106

문제 정책

당신은 주어진 정렬 정수 주어진 배열은 양수와 음수를 모두 포함 할 수 있습니다. 최대 합으로 부분 배열의 크기를 찾으십시오.

arr[] = {1,4,-2,-5,2-1,4,3}
4

설명 : 2-1 + 4 + 3 = 8은 길이 4의 최대 합입니다.


arr[] = {2,-4,1,2,-3,-4}
2

설명 : 1 + 2 = 3은 길이 2의 최대 합입니다.

암호알고리즘

1. Set the maxVal to the minimum value of an integer and maxPoint to 0, start, end, and s to 0.
2. Starting from i=0 to i<size(length of the array).
  1. Sum up the value of maximumPoint and arr[i] and store into the maximumPoint.
  2. Check if maxVal is less than maxPoint, then update the following:
    maxVal = maxPoint
    start=s
    nd=i
  3. Check if the maximumPoint is less than 0, then update
    maximumPoint=0
    s=i+1
3. Return the value (end – start + 1).

최대 합을 사용하여 부분 배열의 크기를 계산하는 방법에 대한 설명

정수 배열이 주어집니다. 우리의 임무는 최대 합이있는 하위 배열. 음수와 양의 정수도 포함 할 수 있습니다. 우리는 가고있다 횡단 전시회는 단 한 번만 이어지며 O (n)의 시간 복잡도를 갖습니다. 찾기 가장 큰 선형 시간 복잡성의 하위 값 합계.

다음과 같이 변수의 특정 값을 설정합니다. 최대값 최소값으로 정수, 최대점 0으로, 스타트, 종료의 메이크업 시연, 그리고 한국에서 사랑을 담아 보낸 s 길이 n까지 배열 탐색을 시작합니다. 루프에서 i 값이 증가 할 때마다 현재 배열 요소를 총 maxPoint에 포함하고 maxPoint에 저장합니다.

maxValue의 값을 Integer의 최소값으로 설정하고 maxValue가 maxPoint보다 크지 않을 가능성이 없는지 확인합니다. 유효한 경우 해당 시점에서 maxPoint에서 maxValue의 값을 업데이트합니다. start to s,이 시작 변수는 인접한 하위 배열의 시작 범위 값을 설정하고 끝이 있습니다. i로 업데이트 할 것입니다.

이제 maxPoint가 0보다 작은 지 확인합니다. 이것은 하위 배열의 합이 음수임을 의미합니다. 그 시점에서 maxPoint의 값을 0으로, s를 i + 1로 다시 업데이트 할 것입니다.이 's'는 시작 범위의 값을 설정하는 데 다시 도움을 주시고 가장 큰 합계 하위 배열을 찾는 데 도움을주세요. 이 maxPoint는 가장 큰 합계를 찾아야하기 때문에 1으로 초기화하고 나중에 값을 end-start + XNUMX로 반환 할 것입니다. 이 반환 값은 최대 합계의 가장 큰 하위 배열 길이입니다.

최대 합이있는 부분 배열의 크기

최대 합이있는 부분 배열의 크기를 찾기위한 C ++ 구현

#include<bits/stdc++.h>

using namespace std;

int getSizeMaxSum (int arr[], int size)
{
    int maxVal = INT_MIN, maximumPoint = 0,
        start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maximumPoint += arr[i];

        if (maxVal < maximumPoint)
        {
            maxVal = maximumPoint;
            start = s;
            end = i;
        }

        if (maximumPoint < 0)
        {
            maximumPoint = 0;
            s = i + 1;
        }
    }

    return (end - start + 1);
}
int main()
{
    int arr[] = {1, -2, 1, 1, -2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getSizeMaxSum(arr, n);
    return 0;
}
2

 

최대 합계가있는 하위 배열의 크기를위한 Java 구현

class SubArraySizeMaximumSum
{

    public static int getSizeMaxSum (int arr[], int size)
    {
        int maxVal = Integer.MIN_VALUE,
            maximumPoint = 0,start = 0,
            end = 0, s = 0;

        for (int i = 0; i < size; i++)
        {
            maximumPoint += arr[i];

            if (maxVal < maximumPoint)
            {
                maxVal = maximumPoint;
                start = s;
                end = i;
            }

            if (maximumPoint < 0)
            {
                maximumPoint = 0;
                s = i + 1;
            }
        }
        return (end - start + 1);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, -2, 1, 1, -2, 1};
        int n = arr.length;
        System.out.println(getSizeMaxSum(arr, n));
    }
}
2

복잡성 분석

시간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 배열을 한 번만 순회하는 데 단일 루프 만 사용했기 때문에 선형 시간 복잡도 솔루션이되었습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 크기 n의 단일 배열을 사용했기 때문에 선형 공간 복잡성도 있습니다.

Translate »