C++에서 주어진 범위의 최대 부분배열 합

주어진 크기의 정수 요소 배열이 제공됩니다. 작업은 배열의 가능한 인덱스 값에서 시작할 수 있는 주어진 범위 내에서 주어진 배열에서 하위 배열을 구성하여 계산될 최대 합계를 찾는 것입니다.

이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -

에서 - 정수 arr[] ={ 3, 2, -1, 6, 7, 2 }, 정수 처음 =0, 정수 마지막 =5

밖으로 − 주어진 범위에서 최대 하위 배열 합계:19

설명 - 양수 값과 음수 값을 모두 포함하는 배열과 0에서 5까지의 범위, 즉 배열의 모든 인덱스를 포함하는 범위가 제공됩니다. 따라서 최대 합계가 있는 하위 배열은 3 + 6 + 7 + 2 + 2 - 1 즉 19가 될 수 있습니다.

에서 - 정수 arr[] ={-2, 1, 3, 4, 8, 9, 23}, 정수 처음 =0, 정수 마지막 =3

밖으로 − 주어진 범위에서 최대 하위 배열 합계:8

설명 - 양수 값과 음수 값을 모두 포함하는 배열과 0에서 3까지의 범위, 즉 0에서 3까지의 배열 인덱스를 포함하는 범위가 제공됩니다. 따라서 최대 합계가 있는 하위 배열은 1 + 3 + 4, 즉 8이 될 수 있습니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• max_val, max_temp, total, sub_sum을 멤버 변수로 저장할 트리 구조를 구성하고 기본 생성자를 사용하여 max_val, max_temp, sum_sum 및 total을 최대값으로 설정합니다.

• max_val을 max(left.max_val, left.total + right.max_val)로, max_temp를 max(right.max_temp, right.total + left.max_temp)로, total을 다음과 같이 설정하여 트리를 구성할 set_node로 구조의 메서드를 만듭니다. left.total + right.total 및 sub_sum을 max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val})로 지정한 다음 노드를 반환합니다.

• 트리를 구성하는 데 사용할 build_tree 메서드를 만듭니다.

  • IF first =last를 확인하고 total, max_temp, max_val, sub_sum을 arr[first]로 설정하고 반환합니다.

  • build_tree(node, arr, first, temp, 2 * inx) 및 build_tree(node, arr, temp + 1, last, 2 * inx + 1)로 build_tree 메서드를 호출한 다음 node[inx]를 set_nodes( 노드[2 * inx], 노드[2 * inx + 1])

• create_tree로 메소드를 생성하고 temp를 (int)(ceil(log2(size)))로 설정한 다음, tree, arr, 값 0, 배열 크기 -1의 노드 객체를 전달하여 build_tree() 메소드를 호출합니다. 인수로 값 1.

• maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx)

  로 최대 하위 배열 합계를 찾는 메서드를 만듭니다.

  • temp temp가 temp_4보다 크거나 temp_2가 temp_3보다 작은지 확인한 다음 NULL을 반환합니다.

  • temp가 temp_3보다 크고 temp_2가 temp_4보다 작은지 확인한 다음 node[inx]

    를 반환합니다.

  • 메서드를 왼쪽으로 호출하여 maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx) 함수를 호출하고 오른쪽에서 maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1)을 호출합니다. )

  • 결과를 set_nodes(left, right)

    로 설정

  • 결과를 반환합니다.

• maximum_subarray(Tree* node, int first, int last, int size)

  로 메소드 생성

  • 메서드에 대한 호출을 maximum_sub(node, 0, size - 1, first, last, 1)

    로 생성합니다.

  • temp.sub_sum 반환

• main() 함수에서

  • 양수 값과 음수 값이 있는 정수 유형의 배열을 선언하고 배열의 크기를 계산합니다.

  • 첫 번째 인덱스에서 마지막 인덱스까지의 범위를 정의합니다.

  • maximum_subarray(node, first, last, size) 함수를 호출하여 주어진 범위에서 최대 하위 배열 합계를 계산합니다.

예시

#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
struct Tree{
   int max_val;
   int max_temp;
   int total;
   int sub_sum;
   Tree(){
      max_val = max_temp = sub_sum = -MAX;
      total = -MAX;
   }
};

Tree set_nodes(Tree left, Tree right){
   Tree node;
   node.max_val = max(left.max_val, left.total + right.max_val);
   node.max_temp = max(right.max_temp, right.total + left.max_temp);
   node.total = left.total + right.total;
   node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
   return node;
}
void build_tree(Tree* node, int arr[], int first, int last, int inx){
   if(first == last){
      node[inx].total = arr[first];
      node[inx].max_temp = arr[first];
      node[inx].max_val = arr[first];
      node[inx].sub_sum = arr[first];
      return;
   }
   int temp = (first + last) / 2;
   build_tree(node, arr, first, temp, 2 * inx);
   build_tree(node, arr, temp + 1, last, 2 * inx + 1);
   node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}
Tree* create_tree(int arr[], int size){
   int temp = (int)(ceil(log2(size)));
   int n = 2 * (int)pow(2, temp) - 1;
   Tree* node = new Tree[n];
   build_tree(node, arr, 0, size - 1, 1);
   return node;
}
Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx){
   if(temp > temp_4 || temp_2 < temp_3){
      Tree nullNode;
      return nullNode;
   }
   if(temp >= temp_3 && temp_2 <= temp_4){
      return node[inx];
   }
   int mid = (temp + temp_2) / 2;
   Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
   Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
   Tree result = set_nodes(left, right);
   return result;
}
int maximum_subarray(Tree* node, int first, int last, int size){
   Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
   return temp.sub_sum;
}
int main(){
   int arr[] = { 3, 2, -1, 6, 7, 2 };
   int size = sizeof(arr) / sizeof(arr[0]);
   Tree* node = create_tree(arr, size);
   int first = 0;
   int last = 5;
   int sub_sum = maximum_subarray(node, first, last, size);
   cout<< "Maximum Subarray Sum in a given Range is: "<< sub_sum;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Maximum Subarray Sum in a given Range is: 19