Thuật toán tìm dãy con lớn nhất

[haihung_9x]

Dưới đây là code thuật toán tìm dãy con lớn nhất hay nói cụ thể hơn là tìm dãy con có tổng max.

#include <iostream>
using namespace std;

int tong(int a[], int left, int right)
{
    return left==right ? a[left] : a[left]+tong(a, left+1, right);
} 

void main()
{
    int a[100], n,i,j;
	cout<<" Nhap so phan tu cua day: ";
    cin >> n;
    for (i=0; i<n; i++)
		{
		cout<<"A["<<i<<"]=";
		cin >> a[i];
		}
    
    int max = a[0], max1;
    int imax = 0, jmax = 0;
    
    for (i=0; i<n; i++)
        for (j=i; j<n; j++)
        {
            if(i==0 && j==n-1);
            max1 = tong(a, i, j);
            if(max1 > max) {max = max1; imax = i; jmax = j;}
        }
    
    
	    cout<<"Day ban dau la: ";
	    for (i=0; i<n; i++)
		cout<<a[i]<< " ";
        
    cout <<"\nDay con lon nhat(co tong max) la: ";
    for (i=imax; i<=jmax; i++)
    cout<<a[i]<<" ";
	cout<<"Co tong trong so la: "<<max<<endl;
 
}

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

• ký pháp nghịch đảo Ba Lan 24/09/2010
• Đảo ngược số 19/07/2009
• Tính tổ hợp của N chập K 21/07/2009
• Đề Thi :Thuật Toán ngày 16.06.2011 10/06/2011
• Thuật toán tìm dãy con lớn nhất 15/04/2011
• Lập trình Shell !! 07/12/2009
• copy n ki tu chuoi s tu vi tri thu m sang chuoi p(m,n khoi tao = 0) 14/05/2009
• Code desktop nào 27/09/2011
• ".:'Định Nghĩa Giai Thừa':." 26/05/2009
• Số Amstrong 21/07/2009

+1 EXP