Tìm dãy con lớn nhất sử dụng thuật toán chia để trị

Trong một buổi học phân thích và thiết kế giải thuật, thầy có giao cho mình một bài tập và rất nhanh sau đó mình đã cải tiến một thuật toán từ đơn giản để khiến nó trở nên ngầu hơn.

Bài toán:

Cho mảng A[1..n].- Mảng A[p..q] được gọi là mảng con của A, trọng lượng mảng bằng tổng giá trị các phần
tử.
– Tìm mảng con có trọng lượng lớn nhất (1<= p <= q <= n)Để đơn giản ta chỉ xét bài toán tìm trọng lượng của mảng con lớn nhất còn việc tìm vị trí
thì chỉ là thêm vào bước lưu lại vị trí trong thuật toán

Code từ ban đầu chỉ đơn giản như sau:

#include <stdio.h >
#include<iostream>
#include<conio.h>
using namespace std;
#define max 100
int a[max];
int n;
int t1, t2;

int Max(int a, int b)
{
if (a>b) return a;
else return b;
}
// ham input

void Input(){
freopen("input1.txt", "r", stdin);
cin>>n;
cout<<"So phan tu: "<< n <<endl;
// khoi tao mang a
for (int i = 0; i >a[i];
cout<< a[i]<<"	";
}
cout<= i; k--)
{
Sum += a[k];
if (MaxSum < Sum) { MaxSum = Sum; dau = k; }
}
return MaxSum;
}

int  MaxRightVector(int i, int j,int &cuoi) // tim tong max tu i sang phai den j
{
int MaxSum = -INT_MAX;
int Sum = 0;
for (int k = i; k <= j; k++)
{
Sum += a[k];
if (MaxSum  m
// max cua day ben trai
wr = MaxSubVector(m + 1, j, dau2, cuoi2); // day phai bat dau tu m+1 -->j
// max cua day ben phai
wm = MaxLeftVector(i, m,dau3) + MaxRightVector(m + 1, j,cuoi3); // max cua day gop lai
int maxTam = Max(Max(wl, wr), wm); // max cua 3 loai
// Luu vet
if (maxTam == wl){ dau = dau1; cuoi = cuoi1; }
else if (maxTam == wr){ dau = dau2; cuoi = cuoi2; }
else if (maxTam == wm){ dau = dau3; cuoi = cuoi3; }
return maxTam; // => dc max cua day ben trai hoac phai tuong ung
}
}

int main()
{
int dau, cuoi;
Input();
int t=MaxSubVector(0, n - 1,dau,cuoi);
cout << "\nDay con lon nhat:";
for (int i = dau; i <= cuoi; i++)
{
cout << " " << a[i];
}
cout<< endl;
cout<<"\nTong day con lon nhat la "<< t;
return 0;
}

Code này sau khi đã chỉnh sửa

#include <bits/stdc++.h>
 using namespace std;
#define maxn 10000
long long  a[maxn];
int n;
int t1, t2;

int sinhtest()
{
    srand(time(NULL));
    string filein = "input.txt";
    ofstream myfile;
    myfile.open (filein);
    int T = rand()%1000;
    myfile << T << endl;
    while(T--)
    {

        int n = rand()%1000;
        myfile << n << endl;
        for(int i= 1; i<= n ;i++)
            myfile << rand()%100000000 - rand()%100000000 << " ";
        myfile << endl;

    }
    myfile.close();
}

int MaxLeftVector(int i, int j,int &dau)
{
	int MaxSum = -INT_MAX;
	int Sum = 0;
	for (int k = j; k >= i; k--)
	{
		Sum += a[k];
		if (MaxSum < Sum) { MaxSum = Sum; dau = k; }
	}
	return MaxSum;
}

int  MaxRightVector(int i, int j,int &cuoi)
{
	int MaxSum = -INT_MAX;
	int Sum = 0;
	for (int k = i; k <= j; k++)
	{
		Sum += a[k];
		if (MaxSum < Sum) { MaxSum = Sum; cuoi= k; }
	}
	return MaxSum;
}

int MaxSubVector(int i, int j,int &dau,int &cuoi)
{
	int dau1, dau2,dau3,cuoi3, cuoi1, cuoi2;
	if (i == j) {
		dau = i; cuoi = i; return a[i];
	}
	else
	{
		int m = (i + j) / 2;
		int wl, wr, wm;
		wl = MaxSubVector(i, m, dau1, cuoi1);

		wr = MaxSubVector(m + 1, j, dau2, cuoi2);

		wm = MaxLeftVector(i, m,dau3) + MaxRightVector(m + 1, j,cuoi3);
		int maxTam = max(max(wl, wr), wm);

		if (maxTam == wl){ dau = dau1; cuoi = cuoi1; }
		else if (maxTam == wr){ dau = dau2; cuoi = cuoi2; }
		else if (maxTam == wm){ dau = dau3; cuoi = cuoi3; }
		return maxTam;
	}
}

int main()
{
    //sinhtest();
    ifstream readfile;
    readfile.open("input.txt");
    ofstream writefile;
    writefile.open("output.txt");
    int T;
    readfile >> T;
    for (int t = 1; t<= T; t++)
    {
        readfile >> n;

        for (int i= 0; i < n ;i++ ) readfile >> a[i];

        int dau, cuoi;
        int sum= MaxSubVector(0, n - 1,dau,cuoi);
        writefile << "case" << t << ":" << "Tong: " << sum << " - [l:r] = [" << dau << ":" << cuoi << "]\n";
    }

    readfile.close();
    writefile.close();
	return 0;
}


Xin cảm ơn các bạn đã đọc !!

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.