題目是浙大版資料結構視頻里的原題，大意是說給出一個整數序列，讓你求出和最大的連續子序列，最后輸出子序列的和以及子序列的第一個數和最后一個數，如果給出的序列全是負數的話，就輸出0以及整個序列的第一個數和最后一個數，
這道題大致有兩種做法，一種是暴力列舉每一個子序列，當然毫無疑問會超時，還有一種是在線處理，我的在線處理做法是：
-
先定義一個last表示最大子序列的最后一個數，定義一個maxSum表示目前為止最大的子序列的和，定義一個sum用于表示當前子序列的和，
-
從第一個數開始處理，
- 把當前的數加到sum上，如果加上之后sum小于0，說明無論之后的數是什么，加上當前這個序列之后都會比原來的小，那么我們果斷把sum清零，重新開始累計，
- 之后判斷sum是否比maxSum大，如果大的話，我們更新last和maxSum，令last等于當前數的下標，maxSum等于sum，
-
繼續往后處理，直到序列結束，
在上邊那樣處理完后，我們找出最大子序列和的問題是解決了，但還有一個問題，如果序列全是負數的話，sum會是0，last最后也會是0，如果序列中只有負數和0的話，最后的結果也會是sum和last都是0，這樣就會導致兩種情況無法區分，我的解決方法是最后從第1個數開始再找一遍，一旦找到0就可以判定是第二種情況，然后輸出0 0 0，如果沒有找到0，那就按第一種情況輸出，
AC代碼如下
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int arr[10001];
int main()
{
int k;
cin >> k;
for (int i = 0; i < k; i++)
scanf("%d", arr + i);
int sum = 0, maxSum = 0, last = 0, start = 0;
for (int i = 0; i < k; i++)
{
sum += arr[i];
if (sum < 0)
sum = 0;
else if (sum > maxSum)
{
maxSum = sum;
last = i;
}
}
int t = 0;
start = last;
while (start >= 0)
{
t += arr[start];
if (t == maxSum)
break;
start--;
}
if (maxSum == 0)
{
bool flag = false;
for (int i = 0; i < k; i++)
if (arr[i] == 0)
{
printf("0 %d %d", arr[i], arr[i]);
flag = true;
break;
}
if (flag == false)
printf("0 %d %d", arr[0], arr[k - 1]);
}
else
{
printf("%d %d %d", maxSum, arr[start], arr[last]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/53362.html
標籤：其他
上一篇：三維中目前新的技術
下一篇：Gaf格式的影片怎么改變顏色