Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
là một thuật toán đơn giản, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự, cho đến khi toàn bộ dãy được sắp xếp.
Vì tìm kiếm nhị phân cần danh sách đã sắp xếp để biết chắc phần tử cần tìm nằm ở bên trái hay bên phải. Nếu không sắp xếp, ta không thể loại bỏ nửa danh sách một cách chính xác
#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;
}