Nhờ giúp đỡ chương trình tính đoạn con

[Tiger]

Viết chương trình tìm đoạn con có tổng bằng S cho trước, em làm như sau nhưng không cho kq đúng, các bác có cách làm tối ưu hơn ko cho em tham khảo, mới nhập môn nên còn gà mờ, C++ càng tốt ạ

#include <iostream>
#include <fstream>
using namespace std;
int main(){

int mang_so[100];
int n,S,i,j,a,Tong;
Tong=0;
cin>>n>>S;
for (int i=0;i<n;i++){
    cin>>mang_so[i];
}
for (i=0;i<n;i++){
  for (j=0;j<n;j++){
    if (i>j) {
        Tong=0;
        continue;
    }
    else {
        for(a=i;a<j;a++){
            Tong=Tong+mang_so[a];

        }
    }
    if (Tong==S) cout<<i<<"---"<<j<<endl;
      }
}

return 0;
}

http://codepad.org/KcZi3NYI

[Mark (Trịnh Minh Cường)]

Ý bác là nhập vào Tổng S rồi sau đó xét xem trong mảng có đoạn nào mà tổng bằng S và in ra đúng k ??

[Tiger]

Đề đây: Tổng đoạn
Một dãy con gồm các phần tử liên tiếp nhau trong một dãy cho trước được gọi
là đoạn. Cho dãy gồm N số tự nhiên, viết chương trình tìm đoạn ngắn nhất có tổng các
phần tử bằng giá trị K cho trước.
Input: Tập tin văn bản DOAN.INP

• Dòng 1: chứa hai số tự nhiên N, K (1 <= N <= 2000);
• Các dòng tiếp theo: các phần tử của dãy, mỗi phần tử cách nhau một khoảng trắng.
  Output: Tập tin văn bản DOAN.OUT, chứa một dòng duy nhất gồm hai số tự
  nhiên x và b. Trong đó x: là chỉ số đầu đoạn; b: là số phần tử trong đoạn (chiều dài
  đoạn). Nếu tìm không có (vô nghiệm) ghi 0 0.
  ===================

Mình mới tìm cách tìm đoạn con có tổng = S thôi, nhờ bạn.

[Rok_Hoang (Minh Hoàng)]

Bạn nghiên cứu quy hoạch động thử xem

[Gio (Gió)]

Nếu là dãy số không âm thì mình có cách làm như sau:

Biến start=0, end,s=0;
Cho end từ 0->n:

• nếu s < k: s+=a[end]
• nếu s=k. So sánh lấy kq tối ưu. s-= a[start] , start+=1 ( Tính cho lần sau).
• nếu s > k. S-=a[start] , start+=1

Giải thích:
Nếu s < k. Thì tất cả đoạn con [start,end] đều không thoã mãn.
Nếu s=k. Tìm thấy, tính cho lần sau.
Nếu s > k. Tất cả đoạn con bắt đầu từ start và sau end đều lớn hơn k nên không tính các đoan con từ start nữa. Chuyển sang đoạn bắt đầu từ start+1.

dpt O(n)

[Tiger]

Thank các thím