Giúp đỡ bài tập: Tìm đoạn dài nhất có tổng dương

#1

cho mình hỏi bài này làm như thế nào với ạ.mình nghĩ gần 1 tháng rồi mà vẫn không ra ạ

image.png1366×768 85.6 KB

#2

Dùng tổng cộng dồn.

Định nghĩa s[0] = 0, s[i] = a[1] + a[2] + ... + a[i] = s[i-1] + a[i].

-> Tổng các số trong đoạn l, r = a[l] + a[l+1] + ... + a[r] = s[r] - s[l-1]

-> Tổng các số trong đoạn l, r dương <-> s[r] > s[l-1].

từ từ để nghĩ tiếp…

#3

Tìm đoạn dương có chiều dài n, nếu có in ra, kết thúc
Nếu không có, tìm đoạn dương có chiều dài n - 1, nếu có in ra, kết thúc
Nếu không có, tìm đoạn dương có chiều dài n - 2, nếu có in ra, kết thúc
…
Nếu không có, tìm đoạn dương có chiều dài 1, nếu có in ra, kết thúc
Nếu không có, trả lời, kết thúc

2 Likes
#4

Em nghĩ thuật này dễ bị quá thời gian.

#5

Chuyện đó tính sau. Đề bài đâu có giới hạn thời gian

1 Like
#6

Thế thôi, cứ O(n^2) mà quất.

1 Like
#7

Có thể tìm được trong O(nlogn)
giả sử tính được mảng cộng dồn s[i] = sum(a[0:i])
dùng 2 mảng phụ tmp, index để tính đoạn dài nhất: mảng tmp này là mảng giảm

  • Nếu s[i] < tmp.back(): trước đó không có phần tử nào nhỏ hơn: cập nhật thêm vào tmp, cập nhật i vào mảng index(để tính độ dài)
  • Nếu không ta tìm phần tử nhỏ hơn đứng trước của s[i] trong tmp, và sử dụng index để tính xem nó có phải là kết quả tốt nhất không. Ở bước này, s[i] không được thêm vào nữa bởi vì nếu có tmp[j]<s[i] thì đoạn tmp[j] < s[i] <s[k] sẽ dài hơn.
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>

using namespace std;


int main() {
	
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	vector<int> tmp;
	vector<int> index;
	
	int s = 0;
	int best = 0;
	int L = 0;
	int H = 0;
	tmp.push_back(0);
	index.push_back(0);
	for(int i=0;i<n;i++) {
		s+=a[i];
		if(s<tmp.back()) {
			tmp.push_back(s);
			index.push_back(i+1);
		}else{
			if(s == tmp.back()) continue;
			auto it = upper_bound(tmp.begin(),tmp.end(),s,greater<int>());
		
			int index_tmp = distance(tmp.begin(),it);
			
			int base_array_index = index[index_tmp];
			
			if(i+1 - base_array_index>=best ) {
				best = i - base_array_index+1;
				L = base_array_index+1;
				H = i+1;
			}
			
		}
	}
	cout<<L<<" "<<H<<endl;
	
	return 0;
}
2 Likes
Code tìm đoạn liên tiếp dài nhất có tổng dương bị sai
#8 
public class a {

int n= 100;
int[] A= new int[n];
int v= n*(n+1)/2;
int[]tong= new int[v];
int[]length= new int[v];
int count = 0;
int max;
for (iint i=0;i<tong.length ;i++ ) {
	tong[i]=0;
}
for (int i=0;i<A.length-1 ;i++ ) {
	for (int j=i+1;j<A.length ;j++ ) {
		for (int k=i;k<=j ;k++ ) {
			tong[count]+=A[k];
		}
		length[count]=j-i+1;
		count++;
	}
}
max=0;
for (int i=0;i<tong.length ;i++ ) {
	if (tong[i]>0) {
		if (length[i]>max) {
			max=length[i];
		}
	}
}
}

mình mới học nên làm kiểu thủ công: tạo 1 dãy chứa tổng và 1 dãy chưa độ dài các tập con trong chứa các phần tử liên tiếp của mảng A. A có n phần tử thì 2 dãy kia có n(n+1)/2 phần tử. Sau đó duyệt tong[i]>0 để kiếm max của length :smiley:

1 Like
#9

Bài này dùng cây BIT/IT để lấy và cập nhật :v

2 Likes
#11

bạn ơi bài này có thuật o(n) không vậy

#12

Thuật O(n log n) khá ổn rồi, O(n) thì quá khó để thực hiện. Mà limit bài này là n = 60000 nên O(n log n) vẫn chạy tốt, cần gì phải O(n).

#14

Bạn có thể dùng BIT or IT để làm. Với IT(x) là vị trí nhỏ nhất có tổng lớn nhỏ hoặc bằng x update thì khi tới vị trí i có tổng là K thì update từ âm vô cùng đến K , với tổng k đó thì mình querý từ âm vô cùng đến K . NlogN

#16

Thuật có chắc chắn đúng không bạn? Và bạn có chứng minh được thuật của bạn chỉ là O(n) hay không?

#17

Chủ thớt có thể ghi lại đề bài được ko ? Ko hiểu sao ko thể load được ảnh …

#18

Cho a[1…n] thỏa n <= 60000 và abs(a[i]) <= 10000, đặt sum_ij = a[i] + a[i+1] + … + a[j]. Trong các (j, i) để sum_ij > 0, cực đại j - i.

Bài này biến thể của a[i] > a[j] với i < j (prefix sum)

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?