Chương trình C++ tìm tổng mảng con lớn nhất dùng nhị phân

Tìm kiếm nhị phân là thuật toán tìm kiếm nhanh với độ phức tạp O(log n). Thuật toán hoạt động dựa trên nguyên lý chia để trị. Để thuật toán hoạt động đúng, tập dữ liệu phải được sắp xếp.

Tìm kiếm nhị phân tìm một phần tử cụ thể bằng cách so sánh với phần tử giữa. Nếu khớp, trả về chỉ số. Nếu phần tử giữa lớn hơn, tìm trong mảng con bên trái; ngược lại tìm bên phải. Tiếp tục cho đến khi kích thước mảng con bằng 0.

Đây là chương trình tìm tổng mảng con lớn nhất dùng phương pháp tìm kiếm nhị phân.

Thuật toán

Bắt đầu
  Khai báo hàm nguyên maximum() tìm max của hai số nguyên.
  Khai báo val1, val2 kiểu nguyên.
  Truyền làm tham số.
  Kiểm tra max giữa val1 và val2.
  Trả về giá trị max.
Kết thúc
Bắt đầu
  Khai báo hàm nguyên MCS() tìm tổng mảng con lớn nhất chứa phần tử giữa.
  Khai báo mảng array[] và biến l, m, h kiểu nguyên.
  Truyền làm tham số.
  Khai báo biến s, sum_of_left_part kiểu nguyên.
    Khởi tạo s = 0.
    Khởi tạo sum_of_left_part = -1.
  for (int i = m; i >= l; i--)
    s = s + array[i].
  if (s > sum_of_left_part) thì
    sum_of_left_part = s.
    s = 0
  Khai báo biến sum_of_right_part kiểu nguyên.
    Khởi tạo sum_of_right_part = -1.
  for (int i = m+1; i <= h; i++)
    s = s + array[i].
  if (s > sum_of_right_part) thì
    sum_of_right_part = s.
  trả về sum_of_left_part + sum_of_right_part.
Kết thúc
Bắt đầu
  Khai báo hàm nguyên MaximumSum_of_SubArray().
  Khai báo mảng array[] và biến l, h kiểu nguyên.
    Truyền làm tham số.
  Khai báo m kiểu nguyên.
  if (l == h) thì
    trả về array[l].
  m = (l + h) / 2;
  trả về maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h)).
  Khai báo number_of_elements và i kiểu nguyên.
  In "Enter the number of elements of array: ".
  Nhập giá trị number_of_elements.
  Khai báo mảng a[number_of_elements] kiểu nguyên.
  for(i = 0; i < n; i++)
    In "Enter the element of".
    Nhập phần tử mảng.
  In "Maximum sum of Sub-Array is: ".
    In kết quả MaximumSum_of_SubArray(a, 0, n-1).
Kết thúc.

Ví dụ

#include<iostream>
using namespace std;

int maximum(int val1, int val2) // tìm max của hai số nguyên
{
  return (val1 > val2) ? val1 : val2;
}

int MCS(int array[], int l, int m, int h) // tìm tổng mảng con lớn nhất chứa phần tử giữa
{
  int s = 0;
  int sum_of_left_part = -1;
  for (int i = m; i >= l; i--) {
    s = s + array[i];
    if (s > sum_of_left_part)
      sum_of_left_part = s;
  }
  s = 0;
  int sum_of_right_part = -1;
  for (int i = m+1; i <= h; i++) {
    s = s + array[i];
    if (s > sum_of_right_part)
      sum_of_right_part = s;
  }
  return sum_of_left_part + sum_of_right_part; // Trả về tổng phần tử bên trái và phải của giữa.
}

int MaximumSum_of_SubArray(int array[], int l, int h) {
  int m;
  if (l == h)
    return array[l];
  m = (l + h) / 2;
  return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}

int main() {
  int number_of_elements, i;
  cout << "Enter the number of elements of array: ";
  cin >> number_of_elements;
  cout << endl;
  int a[number_of_elements];
  for(i = 0; i < number_of_elements; i++) {
    cout << "Enter the element of " << i+1 << ": ";
    cin >> a[i];
  }
  cout << "\nMaximum sum of Sub-Array is: " << MaximumSum_of_SubArray(a, 0, number_of_elements - 1); // In tổng mảng con lớn nhất.
  return 0;
}

Kết quả

Enter the number of elements of array: 5
Enter the element of 1: 12
Enter the element of 2: 45
Enter the element of 3: 56
Enter the element of 4: 48
Enter the element of 5: 75
Maximum sum of Sub-Array is: 236