หาผลรวมสูงสุดของสับอาร์เรย์เพิ่มขึ้นอย่างเคร่งครัดใน C++

สมมติว่ามีอาร์เรย์ของจำนวนเต็ม n ตัว หาผลรวมสูงสุดของสับอาร์เรย์ที่เพิ่มขึ้นอย่างเคร่งครัด (Strictly Increasing) ดังนั้นถ้าอาร์เรย์เป็น [1, 2, 3, 2, 5, 1, 7] ผลรวมคือ 8 ในอาร์เรย์นี้มีสับอาร์เรย์เพิ่มขึ้นอย่างเคร่งครัด 3 ชุด คือ {1, 2, 3}, {2, 5} และ {1, 7} สับอาร์เรย์ที่มีผลรวมมากที่สุดคือ {1, 7}

เพื่อแก้ปัญหานี้ เราต้องติดตามผลรวมสูงสุดและผลรวมปัจจุบัน สำหรับแต่ละองค์ประกอบ arr[i] หากมันมากกว่า arr[i – 1] เราจะบวกเข้าไปในผลรวมปัจจุบัน มิฉะนั้น arr[i] เป็นจุดเริ่มต้นของสับอาร์เรย์อีกชุดหนึ่ง ดังนั้นเราจะอัปเดตผลรวมปัจจุบันเป็นอาร์เรย์ ก่อนอัปเดตผลรวมปัจจุบัน เราจะอัปเดตผลรวมสูงสุดหากจำเป็น

ตัวอย่าง

#include <iostream> 
using namespace std; 

int maximum(int a, int b) {
    return (a > b) ? a : b;
}

int maximum_sum_incr_subarr(int array[], int n) {
    int max_sum = 0;
    int current_sum = array[0];
    for (int i = 1; i < n; i++) {
        if (array[i - 1] < array[i])
            current_sum = current_sum + array[i];
        else {
            max_sum = maximum(max_sum, current_sum);
            current_sum = array[i];
        }
    }
    return max(max_sum, current_sum);
}

int main() {
    int arr[] = {1, 2, 3, 2, 5, 1, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum sum: " << maximum_sum_incr_subarr(arr, n);
}

ผลลัพธ์

Maximum sum: 8