최대 합계 증가 하위 시퀀스

난이도 쉽게
자주 묻는 질문 아마존 광신자 Microsoft 모건 스탠리 (Morgan Stanley)
배열 동적 프로그래밍조회수 39

문제 정책

당신은 주어진 정렬 정수 귀하의 작업은 하위 시퀀스의 숫자가 순서대로 정렬되어야하는 방식으로 배열 내의 최대 합계 하위 시퀀스를 찾는 것입니다. 분류 증가하는 방식으로. 하위 시퀀스는 초기 배열에서 일부 요소를 제거하면 얻는 시퀀스에 불과합니다.

arr[] = {2,4,5,10,1,12}
33

설명 : {2, 4, 5, 10, 12}의 합계 ⇒ 33. 정렬 조건을 충족하기 위해 인덱스 4 (0 기반 인덱싱)의 요소를 제외한 전체 초기 입력 배열을 가져 왔습니다. 이 하위 시퀀스는 최상의 결과를 제공합니다. 다른 하위 시퀀스는 현재 합계보다 작은 합계가됩니다.

arr[] = {3,5,7,1,20,4,12}
35

설명 : {3, 5, 7, 20}의 합계 ⇒ 35. 여기서 우리는 1과 4를 제거하여 나머지 배열을 정렬했습니다. 그런 다음 나머지 요소는 최대 합계 증가 하위 시퀀스를 만듭니다.

 

최대 합계 증가 하위 시퀀스 알고리즘

1. Declare an array say maxSumIS as the same size as the length of an array.
2. Set the output to 0.
3. Copy each element of an array into the created array.
4. Traverse the array from i=1 to i<n(length of the array)
  Now in another loop, from j=0 to j<i,
    Check if arr[i] is greater than arr[j] and maxSumIS[i] is less than maxSumIS[j]+arr[i]N,
      Then update the value of maxSumIS[i] = maxSumIS[j] + arr[i].
5. Traverse the array, and find out the maximum of all the elements from maxSumIS and return that value.

 

설명

정렬되거나 정렬되지 않을 수있는 정수 배열을 제공했습니다. 서브 시퀀스를 증가시키는 최대 합을 찾으려고합니다. 그것도 증가하는 순서 여야합니다. 그래서 우리는 주어진 배열과 같은 크기로 배열을 만들 것입니다. 그런 다음 출력을 0으로 설정합니다.이 출력 값은 모든 요소 중에서 최대 값을 찾는 데 도움이됩니다.

처음으로 배열을 탐색합니다. 처음은 주어진 배열의 값을 우리가 만든 배열에 복사하는 것입니다. maxSumIS []. 이 maxSumIS [] 조건이 충족 될 때마다 배열이 업데이트됩니다. 따라서 maxSumIS 배열의 첫 번째 인덱스를 사용할 것이므로 먼저 i = 1에서 배열을 탐색합니다. 이것이 우리가 두 번째 루프의 값을 0에서 i로 가져온 이유입니다. 상태를 확인하겠습니다 arr [i]가 arr [j]보다 큰 경우, 또한 maxSumIS [j]는 현재 인덱스 i 및 j에 따라 이전 두 요소의 합보다 작습니다. 두 조건이 모두 충족되면 maxSumIS [i] 값을 현재 두 인덱스 요소의 합인 maxSumIS [j] 및 arr [i]로 업데이트합니다.

이는 최대 합계의 하위 시퀀스를 오름차순으로 만 찾고 싶기 때문에 두 요소를 동시에 사용하는 것입니다.

그런 다음 maxSumIS 배열에 저장하고 업데이트 한 모든 요소의 최대 값을 찾아야합니다. 전체 배열을 순회하거나 함수를 사용하여 최대 수를 찾을 수 있습니다. 그러나 배열 maxSumIS의 모든 요소 중 최대 수를 반환해야합니다.

최대 합계 증가 하위 시퀀스

최대 합계 증가 하위 시퀀스에 대한 코드

C ++ 코드

#include<iostream>
using namespace std;

int getMaximumSumIS(int arr[], int n)
{
    int i, j, output = 0;
    int maxSumIS[n];

    for ( i = 0; i < n; i++ )
        maxSumIS[i] = arr[i];

    for ( i = 1; i < n; i++ )
        for ( j = 0; j < i; j++ )
            if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                maxSumIS[i] = maxSumIS[j] + arr[i];

    // Take the maximum out of all the possible answers
    for ( i = 0; i < n; i++ )
        if ( output < maxSumIS[i] )
            output = maxSumIS[i];

    return output;
}
int main()
{
    int arr[] = {2,4,5,10,1,12};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Total sum of Maximum Sum Increasing Subsequence : " << getMaximumSumIS( arr, n );
    return 0;
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

자바 코드

class MaximumSumIncreasingsubsequence
{
    public static int getMaximumSumIS(int arr[], int n)
    {
        int i, j, output = 0;
        int maxSumIS[] = new int[n];

        for (i = 0; i < n; i++)
            maxSumIS[i] = arr[i];

        for (i = 1; i < n; i++)
            for (j = 0; j < i; j++)
                if (arr[i] > arr[j] && maxSumIS[i] < maxSumIS[j] + arr[i])
                    maxSumIS[i] = maxSumIS[j] + arr[i];

        // Take the maximum out of all the possible answers
        for (i = 0; i < n; i++)
            if (output < maxSumIS[i])
                output = maxSumIS[i];

        return output;
    }
    public static void main(String args[])
    {
        int arr[] = {2,4,5,10,1,12};
        int n = arr.length;
        System.out.println("Total sum of Maximum Sum Increasing Subsequence : "+getMaximumSumIS(arr, n));
    }
}
Total sum of Maximum Sum Increasing Subsequence : 33

 

복잡성 분석

시간 복잡성

여기에 두 개의 중첩 루프가 있습니다. 0에서 n-1 및 내부 루프 0 i. 따라서 알고리즘에는 다항식 시간 복잡성이 있습니다. 의 위에2어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

여기에는 문제에 선형 공간 복잡성을 제공하는 크기 n의 1D 배열 만 있습니다. O (N) 어디에 "엔" 배열의 요소 수입니다.

Translate »