Tổng mảng con tròn tối đa trong C ++

Chúng ta được cung cấp một mảng và nhiệm vụ là tạo các mảng con sao cho tổng các mảng con theo kiểu vòng tròn sẽ dẫn đến giá trị lớn nhất.

Đầu vào - int arr [] ={1, 2, 8, 4, 3, 0, 7}

Đầu ra - Tổng mảng con tròn tối đa là - 22

Giải thích - chúng ta được cho một mảng chứa {1, 2, 8, 4, 3, 0, 7} và mảng con của nó có tổng lớn nhất sẽ là 7 + 1 + 2+ 8 + 4 là 22.

Đầu vào - int arr [] ={2, 5, -1, 6, 9, 4, -5}

Đầu ra - Tổng mảng con tròn tối đa là - 25

Giải thích - chúng ta được cho một mảng chứa {2, 5, -1, 6, 9, 4, -5} và mảng con của nó có tổng lớn nhất sẽ là 4 + 2 + 5 - 1 + 6 + 9 là 25.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập một mảng các phần tử số nguyên có chứa cả giá trị âm và dương.

• Tính kích thước của một mảng.

• Chuyển một mảng và kích thước cho hàm để xử lý thêm.

• Tạo một biến tạm thời dưới dạng tổng và đặt nó thành 0

• Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng

• Bên trong vòng lặp, Đặt tổng với tổng + arr [i]

• Đặt temp =arr [0], temp_2 =arr [0], temp_3 =arr [0], temp_4 =arr [0]

• Bắt đầu vòng lặp FOR từ i đến 1 cho đến hết kích thước của một mảng

• Bên trong vòng lặp đặt temp =max (temp + arr [i], arr [i]), temp_2 =max (temp_2, temp), temp_3 =min (temp_3 + arr [i], arr [i]), temp_4 =min (temp_4, temp_3)

• Kiểm tra kích thước IF ==1 rồi trả về arr [0]

• Kiểm tra tổng IF temp_4 ==rồi trả về temp_2

• Đặt max_sum =max (temp_3, total - temp_4)

• Trả về max_sum

• In kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
   int total = 0;
   for (int i = 0; i < size; i++){
      total += arr[i];
   }
   int temp = arr[0];
   int temp_2 = arr[0];
   int temp_3 = arr[0];
   int temp_4 = arr[0];
   for (int i = 1; i < size; i++){
      temp = max(temp + arr[i], arr[i]);
      temp_2 = max(temp_2, temp);
      temp_3 = min(temp_3 + arr[i], arr[i]);
      temp_4 = min(temp_4, temp_3);
   }
   if (size == 1){
      return arr[0];
   }
   if (temp_4 == total){
      return temp_2;
   }
   int max_sum = max(temp_3, total - temp_4);
   return max_sum;
}
int main(){
   int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Maximum circular subarray sum is: 25