최대 합계 연속 하위 배열

난이도 쉽게
자주 묻는 질문 24 * 7 Innovation Labs 수행자 아마존 드 쇼 팩트 셋 Flipkart 인상 Housing.com MakeMyTrip 메트 라이프 Microsoft 모건 스탠리 (Morgan Stanley) 올라 택시 신탁 오요 룸 알레그로 삼성 스냅 딜 테라 데이타 비자, VM웨어 월마트 연구소 조호 (Zoho)
배열 동적 프로그래밍조회수 40

문제 정책

정수 배열이 제공됩니다. 문제 설명은 가장 큰 합 연속 부분 배열을 찾아야합니다. 이것은 주어진 배열의 다른 모든 하위 배열 중에서 가장 큰 합계를 갖는 하위 배열 (연속 요소)을 찾는 것뿐입니다.

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

설명 : 색인 2에서 색인 4까지의 하위 배열은 배열 내에서 7의 가장 큰 합계를 갖습니다. 다른 하위 배열은 7보다 작은 합계를 제공합니다.

최대 합계 연속 하위 배열

 

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

설명 : 인덱스 2부터 인덱스 6까지의 하위 배열은 배열 내에서 가장 큰 합계가 10입니다.

 

최대 합계 연속 부분 배열 문제에 대한 알고리즘

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

설명

우리는 정렬 정수 우리는 가장 큰 합 연속 부분 배열을 찾기를 요청했습니다. 음수 및 양의 정수도 포함 할 수 있습니다. 우리는 그 모든 사건을 처리해야합니다. 이를 위해 우리는 배열을 한 번만 순회 할 것이므로 복잡한 시간이 있습니다. O (N). 선형 시간 복잡도에서 최대 연속 하위 배열 합계를 찾을 수 있습니다.

다음과 같은 일부 값을 설정하십시오. 최대값 Integer가 보유 할 수있는 최소값으로, 최대점 0으로, 스타트, 종료의 메이크업 시연, 그리고 한국에서 사랑을 담아 보낸 s 0으로. 배열을 길이까지 순회 시작합니다. n. 현재 배열 요소를 합계 maxPoint에 추가합니다. maxPoint에 저장하십시오. i 루프에서 증가하면이 작업을 수행합니다. 우리는 이미 최대값 Integer의 최소값으로 설정하고 maxValue가 maxPoint보다 작은 지 확인합니다. 이것이 참이면 maxPoint에서 maxValue 값을 s로 업데이트합니다. 이 시작 변수는 인접한 하위 배열의 시작 범위 값을 설정하고 끝이 있으며 i (루프 변수)로 업데이트합니다.

지금 확인하겠습니다 최대점 0보다 작 으면 지금까지 배열 값을 더한 값이 음수임을 의미합니다. 그런 다음 다시 maxPoint 값을 0으로, s를 i + 1로 업데이트합니다. 이 s 시작 범위의 값을 설정하는 데 다시 도움이되며 가장 큰 합계 하위 배열을 찾는 데 도움이됩니다. 이 maxPoint는 가장 큰 합계를 찾아야하기 때문에 XNUMX으로 초기화되고 필요한 최대 합계 하위 배열의 시작 및 끝 인디 스로 시작 및 끝 값을 인쇄 할 것입니다. 이 접근 방식을 사용하면 단일 패스에서 가장 큰 합계 연속 하위 배열을 찾을 수 있습니다.

 

최대 합계 연속 부분 배열 문제에 대한 코드

C ++ 코드

#include<bits/stdc++.h>
using namespace std;

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

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

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7

 

자바 코드

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

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

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}
Sub-Array starting from 2 to 4 has a largest sum of 7

복잡성 분석

시간 복잡성

크기 n의 입력 배열에 대해 단일 루프를 실행하고 있기 때문입니다. 따라서 가장 큰 합 연속 부분 배열에 대한 알고리즘은 선형 시간 복잡도를 갖습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

정수를 저장하기 위해 단일 1D 입력 배열을 사용했습니다. 따라서 최대 합 연속 부분 배열 문제에 선형 공간 복잡성을 제공합니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

Translate »