โปรแกรม C++ หาผลรวมสูงสุดของ Subarray ด้วย Binary Search

Binary search เป็นอัลกอริทึมค้นหาที่รวดเร็วด้วยความซับซ้อน O(log n) ทำงานหลักการแบ่งและเอาชนะ (divide and conquer) ต้องการข้อมูลที่เรียงลำดับแล้ว

Binary search เปรียบเทียบค่ากลางของชุดข้อมูล หากตรงกันคืนดัชนี หากค่ากลางมากกว่า ค้นหาในส่วนซ้าย มิฉะนั้นค้นหาในส่วนขวา ทำซ้ำจนขนาด subarray เหลือศูนย์

นี่คือโปรแกรมหาผลรวมสูงสุดของ subarray ด้วยแนวคิด Binary Search

อัลกอริทึม

เริ่มต้น
  ประกาศฟังก์ชัน integer maximum() หาค่าสูงสุดของสองจำนวน
  รับพารามิเตอร์ val1, val2
  ตรวจสอบค่าสูงสุดระหว่าง val1 และ val2
  คืนค่าสูงสุด
สิ้นสุด

เริ่มต้น
  ประกาศฟังก์ชัน integer MCS() หาผลรวมสูงสุดของ sub-array ที่รวมจุดกลาง
  รับพารามิเตอร์ array[], l, m, h
  ประกาศตัวแปร s, sum_of_left_part
    กำหนด s = 0, sum_of_left_part = -1
  สำหรับ (int i = m; i >= l; i--)
    s = s + array[i]
    ถ้า (s > sum_of_left_part) แล้ว
      sum_of_left_part = s
    จบถ้า
  จบลูป
  s = 0
  ประกาศ sum_of_right_part
    กำหนด sum_of_right_part = -1
  สำหรับ (int i = m+1; i <= h; i++)
    s = s + array[i]
    ถ้า (s > sum_of_right_part) แล้ว
      sum_of_right_part = s
    จบถ้า
  จบลูป
  คืนค่า sum_of_left_part + sum_of_right_part
สิ้นสุด

เริ่มต้น
  ประกาศฟังก์ชัน integer MaximumSum_of_SubArray()
  รับพารามิเตอร์ array[], l, h
  ประกาศ m ชนิด integer
  ถ้า (l == h) แล้ว
    คืนค่า array[l]
  จบถ้า
  m = (l + h) / 2
  คืนค่า maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h))
  ประกาศ number_of_elements, i ชนิด integer
  พิมพ์ "Enter the number of elements of array: "
  รับค่า number_of_elements
  ประกาศอาร์เรย์ a[number_of_elements]
  สำหรับ (i = 0; i < n; i++)
    พิมพ์ "Enter the element of "
    รับค่าสมาชิกอาร์เรย์
  จบลูป
  พิมพ์ "Maximum sum of Sub-Array is: "
  พิมพ์ผลลัพธ์ MaximumSum_of_SubArray(a, 0, n-1)
สิ้นสุด

ตัวอย่างโค้ด

#include <iostream>
using namespace std;

int maximum(int val1, int val2) {
    return (val1 > val2) ? val1 : val2;
}

int MCS(int array[], int l, int m, int h) {
    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;
}

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);
    return 0;
}

ผลลัพธ์

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