Tìm dãy số có tổng dương dài nhất.

[integer]

Đề như sau: Cho 1 dãy số nguyên, có giá trị âm và không âm. vd: 1 -2 5 -10 2 33 12 -9 -3.
Viết thuật toán tìm dãy số dài nhất có thể và có tổng dương.

Mình có thuật toán như sau:
- Xét tổng của dãy. Nếu tổng lớn hơn 0 --> dãy dài nhất chính là dãy ban đầu --> xuất ra.
- Nếu tổng nhỏ hơn 0.
- Duyệt từ đầu dãy và, duyệt qua phần từ nào đếm số phần tử và gán số phần tử đã duyệt cho biến i. dừng lại tại giá trị < 0 đầu tiên gặp được.
- Duyệt từ cuối dãy về. đếm số phần tử đã duyệt cho biến j. dừng lại khi gặp giá trị âm đầu tiên
--> Lúc này 2 biến i và j thể hiện vị trí từ đầu danh sách đến số âm đầu tiên đi lên và từ cuối danh sách đến số âm đầu tiên từ cuối về.

Ta xét 2 số i ,j.
i = j => số nào nhỏ hơn thì loại. Mục đích là lấy số lớn hơn. 2 số bằng nhau(trường hợp này mình chưa xét).
i > j. lấy danh sách xuất phát từ đầu đến vị trí j. Vì ta lấy theo tiêu chí là dãy số dài nhất có thể. từ cuối dãy về gặp số âm trước nên loại phần cuối(tính từ j -> hết dãy). tính tổng dãy . nếu dương --> xuất ra, nếu âm --> gọi đệ quy, xét tiếp dãy số còn lại.
i < j. Ngược lại, lấy danh sách mời từ vị trí i -> hết dãy. tính tổng. nếu dương --> xuất kết quả. nếu âm --> gọi đệ quy tính tiếp.

Đây mới là thuật toán sơ bộ, còn nhiều thuật toán khác để làm việc này. mình chưa cài đặt thuật toán này. ai làm rồi cho tham khảo nhé.

--------------------------------------------------
Xem các chủ đề cùng chuyên mục:

• Tích của 2 ma trận 14/05/2009
• Thuật toán tìm dãy con chung dài nhất.. 17/04/2011
• Tìm kiễm chuỗi trong chuỗi 04/03/2011
• Kiểm tra dãy số tăng hay không? 19/07/2009
• ".:'Đề Kiểm Tra Học Kì':." 10/06/2009
• Nhập 1 chuỗi. Các chữ thường => hoa, các chữ hoa => thường rồi xuất ra 21/07/2009
• Lệnh SWITCH một chút vui. 25/05/2009
• Bài Tập Hàm-Bài 31 SGK 21/05/2009
• Bài Tập Hàm-Tổ hợp 21/05/2009
• Bài Tập Hàm-Số Nguyên Tố 21/05/2009

+2 EXP

[integer]

Tân xuân khai bút, nghiệp mình không dùng bút thì chuột và bàn phím
Demo chưa test đâu:

int tong(int m[],int f,int n)
{
    int tong=0;
    for(int i=f; i<n; i++)
        tong+=m[i];
    if(tong>0)
        return tong;
    else return 0;
}
void xuat(int m[],int f,int n)
{
    for(int i=f; i<n; ++)
        cout<<m[i]<<"\t";
}
void nhap(int m[],int n)
{
    cout<<"\nNhap n: ";
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cout<<"Nhap "<<i<<": ";
        cin>>m[i];
    }
}
main ()
{
    int f=0;// vi tri dau tien
    if(tong(m,n)<=0)
        xuat(m,f,n);
    else
    {
        int cfirst=0,clast=0;
        for(int i=0; i<n; i++)
        {
            if(m[i]<0)
                break;
            else
                cfirst++;
        }
        for(int j=n;j>0;j--)
        {
            if(m[j]<0)
                break;
            else
                clast++;
        }
        //xet 2 so i,j
        if(i==j)
            {
                if(m[i]<m[j])
                    {
                        f=i+1;// lay day sau vi tri i den n
                        xuat(m,f,n);
                    }
                else
                    xuat(m,f,(n-j)-1);//n-j la vi tri gap so am dau tien, lay n tai
                                    //loai them phan tu tai vi tri j nua
            }
        if(i>j)
            {
            
            }
    }
}

Khai bút nên làm tạm thế đã, ra tết làm tiếp, chúc mọi người học tốt

[lyvinhr00m]

Tết mà vẫn siêng thế chú