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

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…

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

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

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

Đề bài đâu có giới hạn thời gian

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

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

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;
}

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

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

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

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).

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

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?

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

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.