Mọi người giúp em giải pháp hoặc keywork để tìm giải pháp cho bài toàn này với ạ. Đây là 1 bài toán từ hackerearth.com. Em xin mô tả lại đề bài, em lạc mất cái đề gốc rồi :((. Cho một dãy số có N phần tử. Hãy tìm ra tập con các phần tử có tổng các phần tử là lớn nhất. Trong đó, 1 tập con các phần tử không thể có 1 phần tử lớn hơn tổng của 2 phần tử bất kì trong tập.
Ví dụ [10, 5, 4, 4, 4]
Tập phần tử chính xác là:
[5, 4, 4, 4] => đúng
[10,5,4] => sai ( 10 > 5 + 4)
[4, 4, 4] => đúng
…
Tập phần tử chính xác là: [5, 4, 4, 4]
Tìm tập con có tổng các phần tử là lớn nhất và mỗi phần tử không thể lớn hơn tổng của 2 phần tử bất kì trong tập
Cho mình hỏi lại là tập con hay mảng con? tập con nghĩa là không cần liên tiếp nhau cũng được đúng không? Ví dụ [10 4 4] (sai)
3 Likes
đúng rồi ạ. không cần theo thứ tự.
Sort lại mảng tăng dần.
Nhận thấy là 1 tập (tăng dần)
- có 2 phần tử: luôn thoả mãn đề bài.
- có >= 3 phần tử: chỉ cần phần tử lớn nhất không lớn hơn tổng của 2 phần tử nhỏ nhất là ok.
Không xét trường hợp 2 phần tử, lúc này ta cần tìm 1 đoạn con a[i] -> a[j] mà a[i] + a[i+1] >= a[j]. Dùng binary search để tìm phần tử này, sau đó lấy tổng đoạn con. Cập nhật biến kết quả với tổng đoạn con vừa rồi.
res = 2
sort(a)
for i = 0 -> len(a)-3:
j = tìm_chỉ_số_của_phần_tử_xa_nhất_không_quá(a[i] + a[i+1])
// cẩn thận trường hợp không tìm thấy j
res = max(res, tổng đoạn con từ i -> j)
hoặc
res = 2
sort(a)
a.append(inf) // đề phòng trong lúc tìm kiếm không tồn tại j
for i = 0 -> len(a)-3:
j = tìm_chỉ_số_của_phần_tử_đầu_tiên_lớn_hơn(a[i] + a[i+1])
res = max(res, tổng đoạn con từ i -> j-1)
Cài đặt tổng đoạn con bằng prefix sum để mỗi bước lấy tổng đoạn con chỉ tốn O(1).
Độ phức tạp O(n log n).
3 Likes
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
vector<int> MaxSum(vector<int> &Arr)
{
if (Arr.size() < 3)
{
return Arr;
}
// O(nlogn)
sort(Arr.begin(), Arr.end(), greater<int>());
vector<int> ConsecutiveSum(Arr.size() - 1);
vector<int> CumulativeSum(Arr.size(), 0);
// O(n)
for (int i = 0; i < Arr.size(); ++i)
{
if (i < ConsecutiveSum.size())
{
ConsecutiveSum[i] = Arr[i] + Arr[i + 1];
}
CumulativeSum[i] = i == 0 ? Arr[i] : CumulativeSum[i - 1] + Arr[i];
}
int maxSum = INT_MIN;
int endPos = 0, beginPos = 0;
// O(nlogn)
for (int i = 0; i < Arr.size(); ++i)
{
vector<int>::iterator upper;
upper = upper_bound(ConsecutiveSum.begin(), ConsecutiveSum.end(), Arr[i], greater<int>());
int end = upper - ConsecutiveSum.begin();
int begin = i - 1;
int sum = begin >= 0 ? CumulativeSum[end] - CumulativeSum[begin] : CumulativeSum[end];
if (sum > maxSum)
{
maxSum = sum;
beginPos = begin;
endPos = end;
}
}
cout << "MaxSum:" << maxSum << endl;
vector<int> result(beginPos + 1 + Arr.begin(), endPos + 1 + Arr.begin());
return result;
}
int main() {
//ifstream cin("test.txt");
int n;
cin >> n;
vector<int> Arr(n);
for (int i = 0; i < Arr.size(); ++i)
{
cin >> Arr[i];
}
//cin.close();
vector<int> result = MaxSum(Arr);
for (int i = 0; i < result.size(); ++i)
{
cout << result[i] << " ";
}
system("pause");
return 0;
}
Tại sao phải động vào số thực vậy bạn?
1 Like
Phải đó, mà phép cộng có tính đơn điệu mà 
2 Likes
tại vì khi có >= 2 phần tử trùng nhau thì hàm lower_bound() nó chỉ lấy phần tử đầu tiên. Nên e cộng thêm như vậy để nó lấy xa nhất.
Bạn nên tìm cách khác hay hơn mà không phải động đến số thực. Thêm số thực có thể dẫn đến sai số, có thể sai cả bài.
4 Likes
E có nghĩ đến 1 cách khác là dùng std::map để lưu lại vị trí trùng lớn nhất. Đúng ko a?
Không, bạn có mảng không giảm rồi, ngoài lower_bound còn có upper_bound nữa. Bài này dùng upper là thích hợp.
4 Likes
Lower để nó lấy luôn dấu = nếu có chứ ạ? Dấu = vẫn thỏa mà a?
E cộng delta với delta giảm dần dần mà a
Dùng lower_bound là tìm phần tử đầu tiên >= số đã cho. Thuật toán của bạn sai rồi.
3 Likes
Anh cho e xin 1 test case sai với ạ?
5
1 1 2 3 1
ra 6 (tập [1, 2, 3]) chứ không phải 5 (tập [2, 3])
3 Likes
E có dùng thêm tham số so sánh greater<int>() đó ạ, nên lower_bound() là <= số đã cho. E đã sửa lower lại thành upper rồi ạ. không biết ngoài lỗi đó ra còn sai gì nửa ko a?
Code ok rồi. Không biết bạn xài compiler nào mà mình copy code lên ideone bị báo lỗi thiếu #include <climits> 
3 Likes
visual studio 2017 ạ
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?