Question

Cho dãy số nguyên gồm phần tử. Tìm: Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp) Dãy con gồm các phần tử liên tiếp có tổng lớn nhất. Input Gồm nhiều test, dòng đầu tiên là số lượng test Mỗi bộ test gồm hai dòng: Dòng đầu là số nguyên dương là số lượng phần tử của dãy Dòng tiếp theo gồm số nguyên trong khoảng Output Với mỗi bộ test, in ra trên một dòng, hai số là hai tổng theo yêu cầu. Example Test 1 Input Copy Copy 2 3 4 4 2 5 3 3 -2 3 -4 Output Copy Copy 10 10 9 7 c++ nha

Answer 1

#include <iostream>

#include <vector>

using namespace std;

pair<int, int> findMaxSubarray(vector<int> nums) {

     int n = nums.size();

     int maxSum = nums[0];

     int currentSum = nums[0];

     int start = 0;

     int end = 0;

     for (int i = 1; i < n; i++) {

          if (currentSum < 0) {

               currentSum = nums[i];

               start = i;

               end = i;

          } else {

               currentSum += nums[i];

               end = i;

          }

          if (currentSum > maxSum) {

               maxSum = currentSum;

          }

     }

     return make_pair(start, end);

}

int main() {

     int numTests;

     cin >> numTests;

     for (int t = 0; t < numTests; t++) {

          int n;

          cin >> n;

          vector<int> nums(n);

          for (int i = 0; i < n; i++) {

               cin >> nums[i];

          }

          pair<int, int> maxSubarray = findMaxSubarray(nums);

          cout << maxSubarray.first << " " << maxSubarray.second << endl;

     }

     return 0;

}