題目描述：

給定一個(gè)由N個(gè)整數(shù)元素組成的數(shù)組arr，數(shù)組中有正數(shù)也有負(fù)數(shù)，這個(gè)數(shù)組不是一般的數(shù)組，其首尾是相連的。數(shù)組中一個(gè)或多個(gè)連續(xù)元素可以組成一個(gè)子數(shù)組，其中存在這樣的子數(shù)組arr[i],…arr[n-1],arr[0],…,arr[j]，現(xiàn)在請(qǐng)你這個(gè)ACM_Lover用一個(gè)最高效的方法幫忙找出所有連續(xù)子數(shù)組和的最大值（如果數(shù)組中的元素全部為負(fù)數(shù)，則最大和為0，即一個(gè)也沒(méi)有選）。

輸入：

輸入包含多個(gè)測(cè)試用例，每個(gè)測(cè)試用例共有兩行，第一行是一個(gè)整數(shù)n（1=<n<=100000），表示數(shù)組的長(zhǎng)度，第二行依次輸入n個(gè)整數(shù)（整數(shù)絕對(duì)值不大于1000）。

輸出：

對(duì)于每個(gè)測(cè)試用例，請(qǐng)輸出子數(shù)組和的最大值。

樣例輸入：

6 1 -2 3 5 -1 2 5 6 -1 5 4 -7

樣例輸出：

10 14

根據(jù)上面兩個(gè)所舉的測(cè)試用例，可以發(fā)現(xiàn)[1，-2，3，5，-1，2]中最大子數(shù)組去掉的是-2，而[8，-10，60，3，-1，-6]中最大子數(shù)組排除的是-10，這兩個(gè)有什么特點(diǎn)？沒(méi)錯(cuò)，這兩個(gè)數(shù)都是兩個(gè)數(shù)組中“最小”的，所以，類(lèi)似的，像之前講過(guò)的撈魚(yú)問(wèn)題，我們找最大子數(shù)組的對(duì)偶問(wèn)題——最小子數(shù)組，有了最小子數(shù)組的值，總值減去它不就可以了么？但是我又想，這個(gè)對(duì)偶問(wèn)題只能處理這種跨界的特殊情況嗎？答案是肯定的，如果最大子數(shù)組跨界，那么剩余的中間那段和就一定是最小的，而且和必然是負(fù)的；相反，如果最大子數(shù)組不跨界，那么總值減去最小子數(shù)組的值就不一定是最大子數(shù)組和了，例如上面我們的例子[8，-10，60，3，-1，-6]，最大子數(shù)組為[8 | 60，3，-1，-6]，而最小子數(shù)組和為[-10]，顯然不能用總值減去最小值。

故，在允許數(shù)組跨界（首尾相鄰）時(shí)，最大子數(shù)組的和為下面的最大值

Maxsum={ 原問(wèn)題的最大子數(shù)組和；數(shù)組所有元素總值-最小子數(shù)組和 }

?

1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 5 int n; 6 int a[100000]; 7 8 void getRes() { 9 int max = 0, min = 0, max_tmp = 0, min_tmp = 0, sum = 0; 10 for (int i = 0; i < n; ++i) { 11 sum += a[i]; 12 max_tmp += a[i]; 13 min_tmp += a[i]; 14 if (max_tmp < 0) max_tmp = 0; 15 if (min_tmp > 0) min_tmp = 0; 16 max = max > max_tmp ? max : max_tmp; 17 min = min < min_tmp ? min : min_tmp; 18 } 19 20 int res = max > (sum - min) ? max : (sum - min); 21 cout << res << endl; 22 } 23 24 int main() { 25 //freopen("input.txt", "r", stdin); 26 while (cin >> n) { 27 for (int i= 0; i < n; ++i) { 28 cin >> a[i]; 29 } 30 getRes(); 31 } 32 return 0; 33 } 34 35 /************************************************************** 36 Problem: 1527 37 User: hupo250 38 Language: C++ 39 Result: Accepted 40 Time:150 ms 41 Memory:1908 kb 42 ****************************************************************/

?

總結(jié)

以上是生活随笔為你收集整理的[Jobdu] 题目1527：首尾相连数组的最大子数组和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。