สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม n ค้นหาผลรวมสูงสุดของอาร์เรย์ย่อยที่เพิ่มขึ้นอย่างเคร่งครัด ดังนั้นหากอาร์เรย์เป็นแบบ [1, 2, 3, 2, 5, 1, 7] ผลรวมคือ 8 ในอาร์เรย์นี้มีอาร์เรย์ย่อยที่เพิ่มขึ้นอย่างเคร่งครัดสามชุด ได้แก่ {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
