d784 - 一、連續元素的和
題目描述
題目要求找出一個整數數列中，連續元素的和的最大值。輸入包含多組測試資料，每組資料包含數列長度 n 和 n 個整數。對於每組資料，輸出數列中連續元素的和的最大值。
解題思路
這題可以使用動態規劃 (Dynamic Programming) 或貪心算法 (Greedy Algorithm) 解決。程式碼採用了類似動態規劃的思路，但實現方式較為直接。外層迴圈遍歷數列的起始位置 i，內層迴圈遍歷數列的結束位置 j。對於每個起始位置 i，計算從 i 到 j 的連續元素和，並更新 ans[i] 為目前找到的最大值。最後，遍歷 ans 數組，找出全局最大值。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int a;
cin >> a;
while(a--){
int b,max=-10000;
cin >> b;
int c[b+1]={0},ans[b+1]={0};
for(int i=0;i<b;i++){
cin >> c[i];
ans[i]=-10000;
}
for(int i=0;i<b;i++){
for(int j=i+1;j<=b;j++){
if(c[i]>ans[i])
ans[i]=c[i];
c[i]+=c[j];
}
}
for(int i=0;i<b;i++){
if(ans[i]>max)
max=ans[i];
}
cout << max << "\n";
}
}