T.18 Dãy con có tích lớn nhất

T.18 Dãy con có tích lớn nhất
Cho N và dãy a1, a2, ..., aN.
Hãy tìm dãy con có tích lớn nhất.
Dữ liệu: Vào từ tệp PERSEQ.INP gồm
Dòng 1: Ghi số nguyên dương N (N <=10^5)
Dòng 2: Ghi N số nguyên a[i] (a[i] <= 10^9).
Kết quả: Ghi ra tệp PERSEQ.OUT giá trị lớn nhất tìm được.
PERSEQ.INP
5
-1 2 -4 -5 3
PERSEQ.OUT
120

Code:

#include <bits/stdc++.h>
#define nmax 10005

using namespace std;

int n;
int a[nmax];

void find() {
   int best = INT_MIN, s = 1;
   for (int i = 1; i <= n; i++) {
       s = max(a[i], s * a[i]);
       best = max(best, s);
   }
   cout << best << "\n";
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("PERSEQ.INP", "r", stdin);
freopen("PERSEQ.OUT", "w", stdout);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
   find();
   return 0;
}

Cách 1: Áp dụng phương pháp sinh dãy nhị phân có độ dài N.
Với mỗi cấu hình ta thực hiện:
for(i, 1, n)
 if (b[i] == 1) t*=a[i];
res = max(res, a[i]);

Độ phức tạp của thuật toán: O(2^n)
Video hướng dẫn Cách 1:

Cách 2: ?
Nếu số lượng phần tử là số âm là chẵn thì return tích tất cả các phần tử.
Còn lại, thực hiện:
Phân rã bài toán:
- Gọi S[i] là tích lớn nhất khi đi đến vị trị i.
+ a[i] có tham gia vào dãy kết quả: s[i-1]*a[i];
+ a[i] không tham gia vào dãy kết quả: a[i];
Tổng hợp lời giải:
- s[i] = max(s[i-1]*a[i], a[i]);

Khi đó kết quả của bài toán:  res = max(res,s[i]);

Cách 3:
- Đọc dữ liệu: Đếm số lượng số âm lưu vào d, tính tích các phần tử lưu vào S.
- Nếu d chẵn thì đưa S ra, kết thúc.
ngược lại,
{
tìm rmax; // số âm lớn nhất trong dãy số.
kq = S / rmax; //không chọn số âm lớn nhất.
đưa kq ra.
}
Đọ phức tạp của thuật toán: O(N).

Code này không xử lí được trường hợp 2 số âm bằng nhau ạ :<

Code:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int n,a[100000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    freopen("perseq.inp","r",stdin);
    freopen("perseq.out","w",stdout);
    cin >> n;
    int dem=0,t=1,vt,am=round(-1e9);
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        if (a[i]<0)
        {
            dem++;
            am=max(am,a[i]);
            if (dem%2!=0&&am==a[i]) vt=i;
        }
        t=t*a[i];
    }
    int r1=1,r2=1;
    if (dem%2==0) cout << t; else
    {
        for (int i=1;i<vt;i++) r1=r1*a[i];
        for (int i=n;i>vt;i--) r2=r2*a[i];
        cout << max(r1,r2);
    }
    return 0;
}

Code:

#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll a[N],b[N]; ll res=1; int n,m=0,k=0; bool khong=false;
void inp(){
cin>>n;
for(int i=1; i<=n; i++){
cin>>x;
if(x<0) b[++m]=x;
else if(x>0) a[++k]=x;
else khong=true;
}
}
void solve(){
if(m%2!=0){
sort(b+1,b+m+1);
for(int i=1; i<m; i++) res*=b[i];
for(int i=1; i<=k; i++) res*=a[i];
}else{
for(int i=1; i<=m; i++) res*=b[i];
for(int i=1; i<=k; i++) res*=a[i];
}
if((n<3 && khong && m==1) || n==1 && khong) cout<<0;
else cout<<res;
}
int main(){
freopen("perseq.inp","r",stdin);
freopen("perseq.out","w",stdout);
inp();
solve();
return 0;
}

Video hướng dẫn thuật toán:

Code:

#include <bits/stdc++.h>
#define N 100007
#define ll long long
#define INF 1000000100

using namespace std;

int n, M = -INF;
ll res = 1;

int main () {
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    freopen ("PERSEQ.INP", "r", stdin);
    freopen ("PERSEQ.OUT", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        if (x != 0) {
            res *= x;
            if (x < 0) M = max(M, x);
        }
    }
    if (res >= 0) cout << res;
        else cout << res / M;
    return 0;
}

#include <bits/stdc++.h>
#define nmax 100007
#define For(i, a, b) for(int i = a ; i <= b ; i++)

using namespace std;

long long a[nmax], n;

void find()
{
vector<int> am;
vector<int> duong;
For(i, 1, n)
if(a[i] < 0) am.push_back(a[i]);
else if(a[i] > 0) duong.push_back(a[i]);
long long s = 1;
if(am.size() % 2 == 0)
For(i, 1, n) s *= a[i];
else
{
sort(am.begin(), am.end());
For(i, 0, am.size()-2) s *= am[i];
For(i, 0, duong.size()-1) s *= duong[i];
}
cout << s;
}

int main()
{
freopen("PERSEQ.inp","r",stdin);
freopen("PERSEQ.out","w",stdout);
cin >> n;
For(i, 1, n) cin >> a[i];
find();
return 0;
}