ได้รับอาร์เรย์จำนวนเต็ม ต้องหาผลรวมของสมาชิกที่ติดกัน (contiguous) ที่มีค่ามากที่สุด
ใช้ Dynamic Programming เก็บค่าผลรวมสูงสุดจนถึงพจน์ปัจจุบัน ช่วยหาผลรวม subarray ที่ติดกัน
Input: {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is: 7
อัลกอริทึม
maxSum(array, n)
Begin
tempMax := array[0]
currentMax = tempMax
for i := 1 to n-1, do
currentMax = maximum of (array[i] and currentMax+array[i])
tempMax = maximum of (currentMax and tempMax)
done
return tempMax
End
ตัวอย่างโค้ด (C++)
#include <iostream>
using namespace std;
int maxSum(int arr[], int n) {
int tempMax = arr[0];
int currentMax = tempMax;
for (int i = 1; i < n; i++) {
currentMax = max(arr[i], currentMax + arr[i]);
tempMax = max(tempMax, currentMax);
}
return tempMax;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
cout << "Maximum Sum of the Sub-array is: " << maxSum(arr, n);
}
ผลลัพธ์
Maximum Sum of the Sub-array is: 7
