Maximum Subarray Sum ในช่วงที่กำหนด (Range) ใน C++

ได้รับอาร์เรย์จำนวนเต็ม มีค่าบวกและลบ หาผลรวมสูงสุดของซับอาร์เรย์ในช่วง index ที่กำหนด [first, last] โดยใช้ Segment Tree

ตัวอย่าง

Input: arr[] = {3, 2, -1, 6, 7, 2}, first = 0, last = 5

Output: Maximum Subarray Sum in a given Range is: 19

คำอธิบาย: ครอบคลุมทั้งอาร์เรย์ ซับอาร์เรย์สูงสุด: 3 + 2 + (-1) + 6 + 7 + 2 = 19 (หรือเลือกเฉพาะบวก: 3+6+7+2+2-1=19)

Input: arr[] = {-2, 1, 3, 4, 8, 9, 23}, first = 0, last = 3

Output: Maximum Subarray Sum in a given Range is: 8

คำอธิบาย: ช่วง index 0-3: {-2,1,3,4} ซับอาร์เรย์สูงสุด: 1+3+4 = 8

อัลกอริทึม: Segment Tree แบบเก็บ 4 ค่า

โครงสร้าง Tree เก็บ: max_val (max prefix), max_temp (max suffix), total (sum ทั้งช่วง), sub_sum (max subarray sum)

• set_nodes: รวมโหนดซ้าย/ขวา
  • max_val = max(left.max_val, left.total + right.max_val)
  • max_temp = max(right.max_temp, right.total + left.max_temp)
  • total = left.total + right.total
  • sub_sum = max(left.sub_sum, right.sub_sum, left.max_temp + right.max_val)
• build_tree สร้างต้นไม้แบบทุกรายละเอียด
• maximum_sub query ช่วง [first, last] แบบ recursive
• maximum_subarray คืนค่า sub_sum

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

#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f3f3f

struct Tree {
    int max_val, max_temp, total, 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 = node[inx].max_temp = node[inx].max_val = 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) return Tree();
    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);
    return set_nodes(left, right);
}

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, 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