อาร์เรย์ของจำนวนเต็มจะได้รับ เราต้องหาผลรวมขององค์ประกอบทั้งหมดที่อยู่ติดกัน ผลรวมของใครมากที่สุดจะถูกส่งเป็นผลลัพธ์
การใช้โปรแกรมไดนามิกเราจะเก็บผลรวมสูงสุดจนถึงเทอมปัจจุบัน จะช่วยในการค้นหาผลรวมขององค์ประกอบที่อยู่ติดกันในอาร์เรย์
Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is : 7 อัลกอริทึม
maxSum(อาร์เรย์, 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
ตัวอย่าง
#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++ ) { //find the max value
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
