Tin học Văn bản SUBSEQ

[Nguyễn Trần Phát]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

Cho dãy gồm n số nguyên a1, a2, ..., an. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.
Dữ liệu: Vào từ file văn bản SUBSEQ.INP
- Dòng đầu tiền chứa số nguyên dơng n (n < 102).
- Dòng thứ i trong số n dòng tiếp theo chứa số ai (|ai| <= 1000).
Kết quả: Ghi ra file văn bản SUBSEQ.OUT
- Dòng đầu tiên ghi vị trí của phần tử đầu tiên của dãy con tìm được.
- Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được
- Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.
Ví dụ:

SUBSEQ.INP	SUBSEQ.OUT
8 12 -14 1 23 -6 22 -34 13	3 6 40

[TBODY] [/TBODY]

 

[Duong 2007]

bạn có thể giải thích đề bài đc không ạ mình vẫn chưa hỉu

 

[Nguyễn Trần Phát]

bạn có thể giải thích đề bài đc không ạ mình vẫn chưa hỉu

Tức là tìm một mảng con trong đó mà tổng của các phần tử trong mảng con đó là lớn nhất

 

[7 1 2 5]

Cho dãy gồm n số nguyên a1, a2, ..., an. Tìm dãy con gồm một hoặc một số phần tử liên tiếp của dãy đã cho với tổng các phần tử trong dãy là lớn nhất.
Dữ liệu: Vào từ file văn bản SUBSEQ.INP
- Dòng đầu tiền chứa số nguyên dơng n (n < 102).
- Dòng thứ i trong số n dòng tiếp theo chứa số ai (|ai| <= 1000).
Kết quả: Ghi ra file văn bản SUBSEQ.OUT
- Dòng đầu tiên ghi vị trí của phần tử đầu tiên của dãy con tìm được.
- Dòng thứ hai ghi vị trí của phần tử cuối cùng của dãy con tìm được
- Dòng thứ ba ghi tổng các phần tử của dãy con tìm được.
Ví dụ:

SUBSEQ.INP	SUBSEQ.OUT
8 12 -14 1 23 -6 22 -34 13	3 6 40

[TBODY] [/TBODY]

Ý tưởng:
Ta sẽ xây dựng mảng

v[i]=a[0]+a[1]+...+a[i-1]

với [TEX]i \geq 1[/TEX], v[0]=0
Sau đó ta sẽ cho chạy 2 vòng for:

for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++)
if(v[j] - v[i] >= ans) ans = v[j] - v[i];

Đến đây chỉ cần xuất ans là được.