c907 - 尋找最大矩形
題目描述
題目要求找出一個由 N 個長條圖構成的高度序列中，可以形成的最大矩形面積。每個長條圖的寬度為 1，高度由輸入的 N 個數字決定。
解題思路
此程式碼採用暴力法 (Brute Force) 的方式來解決問題。對於每個高度 a[i]，程式碼嘗試向左右兩側擴展矩形，直到遇到高度小於 a[i] 的長條圖。擴展的過程中，矩形的面積會不斷累加。最後，程式碼會比較所有可能的矩形面積，並輸出最大值。
具體來說，對於每個 a[i]，程式碼會分別向右和向左擴展，計算以 a[i] 為最低高度的最大矩形面積。向右擴展時，只要遇到的高度大於等於 a[i]，就將 a[i] 加到總面積中。向左擴展的邏輯相同。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int n,ans=0;
cin >> n;
int a[n];
for(int i=0;i<n;++i)
cin >> a[i];
for(int i=0;i<n;++i){
int tmp=0;
for(int ii=i;ii<n;++ii){
if(a[ii]>=a[i])
tmp+=a[i];
else
break;
}
for(int ii=i-1;ii>=0;--ii){
if(a[ii]>=a[i])
tmp+=a[i];
else
break;
}
ans=max(ans,tmp);
}
cout << ans;
}