Nhập một mảng n phần tử, Tìm mảng con có số phần tử là m có tổng max
m,n nhập từ bàn phím.

M đã cố viết những nó vẫn ko đúng! Pro nào rảnh thì code giúp mình bài ấy nhé! thanks nhiều!

Dãy LIÊN TỤC:
Xem mã này:

summax=0;
for(i=1,i<n,i++) //n là chặn trên của mảng
{
sumtmp=0;
for{j=i,j<n,j++)
{
sumtmp=sumtmp+a(j);
if (sumtmp>summax)
{
summax=sumtmp;
posstart=i
posend=j
}
}
}

Kết quả nằm trong biến posstart và posend (posstart là vị trí bắt đầu, posend là vị trí kết thúc của dãy có tổng max.

Còn dãy KO LIÊN TỤC thì dùng đệ quy quay lui.

Bài tập yêu cầu số luong pt của dãy con m nhập từ bàn phím.
Phần này m hơi đuối! Bạn sửa lại giúp m nhé!
Thân!

Dãy liên tục thì sửa hàng
for{j=i,j<n,j++)
thành:
if i+m<n then break;
for{j=i,j<i+m,j++)
còn đệ quy thì cũng thế.

Thanks cậu nhé!

Nếu là mảng con liên tục thì e rằng người ra bài muốn chấm 50% cách giải và 50% cách viết code.

Giải bài thế này:

1. nếu mảng con bắt đầu từ r1 và kết thúc ở r2 thì tổng trị số là
sameTypeAsArrayElement sum = 0;
for (int i = r1; i <= r2; i++) sum += a[i];

2. mảng con kế tiếp bắt đầu từ r1+1 và kết thúc ở r2+1
Như vậy để tính tổng của mảng kế tiếp, ta không cần lặp lại cách tổng trên, mà chỉ cần trừ đi phần tử đầu và cộng thêm phần tử kế
sumNext = sum – a[r1] + a[r2+1];

3. Di mảng con từ từ:
(phương pháp giữ số max/min là chuyện thông thường)

4. r2 = r1 + độ dài mảng con - 1

Code:
// đã có sẵn array a[], n là cỡ mảng lớn, n là cỡ mảng con
// code này không có check trường hợp m > n
// phần tử của a có thể là int, float, miễn là số
sameTypeAsArrayElement sum = 0;
int r = 0; // chuỗi con ở vị trí bắt đầu tức là 0
for (int i = 0; i < m; i++) sum += a[i];
sameTypeAsArrayElement sumMax = sum;
// vòng sau đây di chuỗi con từ vị trí 1 đến vị trí cuối có thể được
for (int i = 1; i <= n-m; i++)
// khi i = n-m, phần tử cuối của chuỗi con cũng là phần tử cuối chuỗi lớn
{
sum = sum + a[i+m-1] – a[i-1];
if (sum > sumMax) // tìm được sumMax mới
{
sumMax = sum;
r = i;
}
}
// r là vị trí bắt đầu của mảng con cần kiếm, vị trí cuối là r + m -1

*** Nếu mảng không liên tục thì bí, không rõ cách đệ quy hay hơn hay sort array tốt hơn.

Array sort + bảng key (nếu cần xuất vị trí) đảm bảo ăn đứt đệ wy (bubble sort có O(n^2) còn đệ we là O(n!) đã vậy còn ăn stack vô địch).
Viết theo kiểu của pác với số phần tử bất kì:

summax=-infinite
for (i=1,i<n,i++)
{
sumtemp=0
for (j=1,j<i,j++)
sumtemp=sumtemp+a[j];
if (sumtemp>summax) summax=sumtemp;
for (j=i,j<n-i,j++)
sumtemp=sumtemp-a(1)+a(j+1)
if (sumtemp>summax) summax=sumtemp;
}
//tự tính 1...n
O(n^2)
cách cũ của tui cũng O(n^2);-)

Các bạn kia đưa code ra nhưng chưa nói đến trường hợp mảng nhập vào có giá trị âm-dương xen kẽ thì sao nhỉ?:)
- Bài này khá dài, mình lười code lại quá !