【題解】Zerojudge i402 - 4. 內積

題目連結

題目大意

給定兩個數列 $a_1, \dots, a_n$ 和 $b_1, \dots, b_m$，你可以翻轉數列。你的目標是選擇一個 $r$ 使得從 $a$ 和 $b$ 各自取一段長度為 $r$ 的子區間且這兩個子區間的內積最大。

• $1 \leq n, m \leq 1000$

題解

內積是每一項各自相乘後加起來，因此固定 $a$ 和 $b$ 的子區間後求內積最大其實就是在求最大連續和的問題，可以參考我先前寫的【題解】LeetCode - 53. Maximum Subarray 這篇文章，該文章詳細介紹了兩種做法。回到本題，我們枚舉 $a$ 子區間的開頭與 $b_1$ 去對齊，一共有 $O(n)$ 種，每次求最大連續和為 $O(max(n, m))$，因此這個做法的時間複雜度為 $O(n \cdot max(n, m))$。最後要記得 $4$ 種翻轉情況都要嘗試，也就是 $\text{"a 正 b 正"}$、$\text{"a 正 b 反"}$、$\text{"a 反 b 正"}$、$\text{"a 反 b 反"}$。其他實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> a, vector<int> b) {
	int ans = INT_MIN;
	for(int i = 0; i < (int) a.size(); i++) {
		int sum = 0;
		for(int p = i, q = 0; p < (int) a.size() && q < (int) b.size(); p++, q++) {
			if(sum < 0) {
				sum = 0;
			}
			sum += a[p] * b[q];
			ans = max(ans, sum);
		}
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> b(m);
	for(int i = 0; i < m; i++) {
		cin >> b[i];
	}
	int ans = INT_MIN;
	for(int mask = 0; mask < 4; mask++) {
		if(mask & 1) {
			reverse(a.begin(), a.end());
		}
		if(mask >> 1 & 1) {
			reverse(b.begin(), b.end());
		}
		ans = max(ans, solve(a, b));
		if(mask & 1) {
			reverse(a.begin(), a.end());
		}
		if(mask >> 1 & 1) {
			reverse(b.begin(), b.end());
		}
	}
	cout << ans << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge i402 - 4. 內積