คำชี้แจงปัญหา
จากอาร์เรย์ของจำนวนเต็มบวกและจำนวนเต็มลบ ให้หาผลรวมของ Subarray สูงสุดในอาร์เรย์นั้น
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น − {-12, -5, 4, -1, -7, 1, 8, -3} ดังนั้นเอาต์พุตจะเป็น 9
อัลกอริทึม
-
คำนวณผลรวมนำหน้าของอาร์เรย์อินพุต
-
Initialize− min_prefix_sum =0, res =-อนันต์
-
รักษาลูปสำหรับ i =0 ถึง n (n คือขนาดของอาร์เรย์อินพุต)
-
cand =prefix_sum[i] – มินิ
-
ถ้า แคน มากกว่า res (ผลรวมของ subarray สูงสุดจนถึงตอนนี้) จากนั้นให้อัปเดต res ด้วย cand
-
หาก prefix_sum[i] น้อยกว่า min_prefix_sum (ยอดรวมคำนำหน้าขั้นต่ำจนถึงตอนนี้) ให้อัปเดตmin_prefix_sumตาม prefix_sum[i]
-
-
ผลตอบแทน
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
int minPrefixSum = 0;
int res = numeric_limits<int>::min();
int prefixSum[n];
prefixSum[0] = arr[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}
for (int i = 0; i < n; i++) {
res = max(res, prefixSum[i] - minPrefixSum);
minPrefixSum = min(minPrefixSum, prefixSum[i]);
}
return res;
}
int main(){
int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Result = 9
