i429 - 4. 內積 (時限放寬版，給 Python 使用者)
題目描述
題目要求在兩個陣列 A 和 B 中分別找到一個長度相同的子區間，使得這兩個子區間的內積最大化。可以對 A 和 B 進行翻轉。
解題思路
程式碼的核心思想是枚舉所有可能的子區間長度，並計算所有可能的子區間組合的內積。為了找到最大內積，程式碼使用了類似 Kadane's Algorithm 的方法，在遍歷子區間時，維護一個當前和，並在當前和變為負數時重置為 0。程式碼還考慮了翻轉陣列 A 的情況，以找到最佳的子區間組合。
具體來說，程式碼首先計算原始陣列 A 和 B 的內積矩陣 dp[i][j] = a[i] * b[j]。然後，它遍歷所有可能的起始位置 i 和 j，計算長度為 r 的子區間的內積，並使用 Kadane's Algorithm 找到最大內積。最後，程式碼翻轉陣列 A，並重複相同的過程，以確保找到全局最大內積。
複雜度分析
- 時間複雜度: O(nmmin(n,m))。外層迴圈遍歷所有可能的起始位置，內層迴圈計算子區間的內積。
- 空間複雜度: O(nm)。程式碼使用了一個大小為 nm 的二維陣列
dp來儲存內積。
程式碼
#include <iostream>
using namespace std;
long n,m,a[1005],b[1005],dp[1005][1005],ans=-1e9;
int main(){
cin.tie(0); ios::sync_with_stdio(0);
cin >> n >> m;
for(int i=0;i<n;++i)
cin >> a[i];
for(int i=0;i<m;++i)
cin >> b[i];
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
dp[i][j]=a[i]*b[j];
for(int i=0;i<n;++i){
long tmp=0;
for(int j=0;i+j<n&&j<m;++j){
tmp+=dp[i+j][j];
ans=max(ans,tmp);
if(tmp<0)tmp=0;
}
}
for(int j=0;j<m;++j){
long tmp=0;
for(int i=0;i<n&&i+j<m;++i){
tmp+=dp[i][i+j];
ans=max(ans,tmp);
if(tmp<0)tmp=0;
}
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
dp[i][j]=a[n-i-1]*b[j];
for(int i=0;i<n;++i){
long tmp=0;
for(int j=0;i+j<n&&j<m;++j){
tmp+=dp[i+j][j];
ans=max(ans,tmp);
if(tmp<0)tmp=0;
}
}
for(int j=0;j<m;++j){
long tmp=0;
for(int i=0;i<n&&i+j<m;++i){
tmp+=dp[i][i+j];
ans=max(ans,tmp);
if(tmp<0)tmp=0;
}
}
cout << ans;
}