do k <= n, nên O(K + log(n)) cũng là O(n) thôi,. Hơn nữa dùng 2 pointer nó đơn giản,đỡ nhức đầu.
xài deque O(k) mem là dỏm ròi O(1) đâu
chơi thêm 2 cái if cho đỡ nhức đầu
Cách của thím là search để lấy điểm ở giữa rồi mở rộng ra 2 bên. Còn cách dùng 2 pointers thì thu hẹp lại để ra được K. Nếu như K lớn, gần = n thì cách dùng 2 pointers sẽ nhanh hơn và ngược lại. Còn worst case thì 2 cách đều như nhau, đều là O(n) cả thôi.
Cách của thím là search để lấy điểm ở giữa rồi mở rộng ra 2 bên. Còn cách dùng 2 pointers thì thu hẹp lại để ra được K. Nếu như K lớn, gần = n thì cách dùng 2 pointers sẽ nhanh hơn và ngược lại. Còn worst case thì 2 cách đều như nhau, đều là O(n) cả thôi.
dãy con có các phần tử liên tục thì cứ chạy vòng for tìm hết các dãy con này là được thoyBài 7. Nhập một dãy số nguyên và lưu trong một mảng. Không dùng mảng trung gian, hãy in ra dãy con tăng nghiêm ngặt có tổng giá trị các phần tử lơn nhất. VD: 1 3 2 8 10 12 7 29 6 6 3 output: 7 29
Bác có ý tưởng làm bài này không bác, mình nghĩ mãi không ra
Mình thấy không đơn giản như bác nghĩ đâudãy con có các phần tử liên tục thì cứ chạy vòng for tìm hết các dãy con này là được thoy
Chính xác là so sánh k + log(n) với n-k.có thể làm thêm cái if check k với n-k cái lào nhỏ hơn thì chọn
1 3 2 8 10 12 7 29 6 6 3 thì có các dãy con tăng nghiêm ngặt làMình thấy không đơn giản như bác nghĩ đâu
mình cũng nghĩ như bác thế nhưng bây giờ chưa biết code kiểu gì1 3 2 8 10 12 7 29 6 6 3 thì có các dãy con tăng nghiêm ngặt là
1 3
2 8 10 12
7 29
6
6
3
ròi tìm dãy con có tổng max là xong
chuẩn rồi, bài này TC=O(n), SC=O(1).1 3 2 8 10 12 7 29 6 6 3 thì có các dãy con tăng nghiêm ngặt là
1 3
2 8 10 12
7 29
6
6
3
ròi tìm dãy con có tổng max là xong
log(n) cũng đâu chính xác, n-k kia so sánh abs() < abs() hoặc có tối ưu thì cũng là int-int < int-int thì lâu hơn 1 cái so sánh trong tìm kiếm nhị phân log(n) chỉ so sánh int < int thoy màChính xác là so sánh k + log(n) với n-k.
là sao bác ?
Đoạn tính tổng thì đơn giản rồi, nhưng làm sao từ cái tổng đấy in ngược ra được cái phần tử con ấy cơ1 3 2 8 10 12 7 29 6 6 3 thì có các dãy con tăng nghiêm ngặt là
1 3
2 8 10 12
7 29
6
6
3
ròi tìm dãy con có tổng max là xong
Cái vụ abs thì có thể tối ưu bằng cách check thêm 2 trường hơn x >= arr.back() hoặc x <= arr.front() là đc.
lưu 2 cái index là đc.
vector<int> getMaxSubArr(const vector<int> &arr) {
if (arr.empty()) return {};
int start = 0, end = 0, start_tmp = 0;
int curMax = std::numeric_limits<int>::min();
int curSum = arr[0];
for (int i = 1; i < arr.size(); ++i) {
if (arr[i] > arr[i-1]) {
curSum += arr[i];
} else {
if (curSum > curMax) {
curMax = curSum;
end = i;
start = start_tmp;
}
start_tmp = i;
curSum = arr[i];
}
}
return vector<int>(arr.begin() + start, arr.begin() + end);
}
Thank 2 bác, để e ngồi ngẫm đãStrict increasing thì các số trong mảng con sẽ là unique, khi thím lưu max(sum) thì lưu thêm cái item cuối cùng. Sau khi loop lần 1 để tìm max(sum) và latest_item thì loop lại 1 lần nữa quay lui để in ra mảng con.
PS: lâu lắm mới mò vào lại thớt này, anh em vẫn xôm tụ nhỉ
