回復 1# may - #include <bits/stdc++.h>
- ///#include <iostream>
- //#include <vector>
- //#include <sstream>
- using namespace std;
- void findMaxSubarray(const vector<int>& nums) {
- int max_sum = nums[0], current_sum = nums[0];
- int start = 0, end = 0, temp_start = 0;
- for (int i = 1; i < nums.size(); i++) {
- if (current_sum < 0) { // 若之前的和小於 0，重新計算
- current_sum = nums[i];
- temp_start = i; // 可能的新起點
- } else {
- current_sum += nums[i]; // 累加當前數值
- }
- if (current_sum > max_sum) { // 更新最大值
- max_sum = current_sum;
- start = temp_start;
- end = i;
- }
- }
- cout << max_sum << endl;
- cout << start << endl;
- cout << end << endl;
- }
- int main() {
- string input;
- getline(cin, input);
- stringstream ss(input);
- vector<int> nums;
- int num;
- while (ss >> num) {
- nums.push_back(num);
- }
- if (nums.empty()) return 0;
- findMaxSubarray(nums);
- return 0;
- }
程式解釋
讀取輸入：使用 getline(cin, input) 讀取一整行數字，並用 stringstream 解析成 vector<int>。
Kadane's Algorithm 來找出最大連續子陣列和：
current_sum 記錄目前子陣列的和，若 current_sum 變成負數，則從當前數字重新計算。
max_sum 記錄最大和，並更新 start 和 end 位置。
輸出結果：
第 1 行：最大連續子陣列總和。
第 2 行：最大連續子陣列起始索引（0-based）。
第 3 行：最大連續子陣列結束索引（0-based）。
-------------------------------------------------------------
測資
測試 00：基本測試
輸入0
-4 1 2 9 -5
輸出
12
1
3
測試01：全為負數
輸入
-5 -2 -8 -1 -7
輸出
-1
3
3
說明：最大連續子陣列為 -1（單獨的一個數），位置為索引 3。
測試 02：全為正數
輸入
3 5 7 2 8 10
輸出
35
0
5
說明：所有數字都是正數，因此最大子序列就是整個數列。
測試03：含有 0
輸入
-3 4 0 5 -2 6 -8 9 0 3 -1
輸出
12
1
5
說明：最大連續子序列為 4 0 5 -2 6，總和 12。
測試04：長度較大的測試
輸入
1 -2 3 10 -4 7 2 -5 8 -1 6 -3 5 9 -6 4 -7 8 0 -2
輸出
21
2
12
說明：最大連續子序列為 3 10 -4 7 2 -5 8 -1 6，總和 21。
這些測試資料涵蓋：
正數、負數、混合數列
含 0 的情境
不同長度的數列
這樣就能確保你的程式能正確運作！ |
