Tổng mảng con tối đa bằng O (n) sử dụng tổng tiền tố trong C ++

Tuyên bố vấn đề

Cho một mảng gồm các số nguyên dương và âm, hãy tìm ra Tổng của mảng con tối đa trong mảng đó

Ví dụ

Nếu mảng đầu vào là - {-12, -5, 4, -1, -7, 1, 8, -3} thì đầu ra là 9

Thuật toán

• Tính tổng tiền tố của mảng đầu vào.

• Khởi tạo− min_prefix_sum =0, res =-infinite

• Duy trì một vòng lặp cho i =0 đến n. (n là kích thước của mảng đầu vào).

  • cand =prefix_sum [i] - mini

  • Nếu cand lớn hơn res (tổng mảng con tối đa cho đến nay), sau đó cập nhật res theo cand.

  • Nếu prefix_sum [i] nhỏ hơn min_prefix_sum (tổng tiền tố tối thiểu cho đến nay), thì updatemin_prefix_sum bằng prefix_sum [i].

• Trả lại res

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -

Result = 9