一个序列长度最大为 $10^5$，每个数都是整数，分割为多段且不改变顺序，求每段之积之和最大值，目前只能想出来 $O(N^2)$ 的做法，有 $O(n\log n)$ 以内的做法吗，或者一些玄学的做法，或者说此题不可做。

$O(N^2)$ 做法：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int n,a[N],dp[N],q[N];
signed main(){
	//freopen("xx.in","r",stdin);
	//freopen("xx.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	q[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		q[i]=q[i-1]*a[i];
	}
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i]=max(dp[i],dp[j-1]+q[i]/q[j-1]);
		}
	}
	cout<<dp[n];
	return 0;
}