https://pintia.cn/problem-sets/15/problems/709

給定K個整數(shù)組成的序列{?N?1??,?N?2??, ...,?N?K???}，“連續(xù)子列”被定義為{?N?i??,?N?i+1??, ...,?N?j???}，其中?1。“最大子列和”則被定義為所有連續(xù)子列元素的和中最大者。例如給定序列{ -2, 11, -4, 13, -5, -2 }，其連續(xù)子列{ 11, -4, 13 }有最大的和20。現(xiàn)要求你編寫程序，計算給定整數(shù)序列的最大子列和。

本題旨在測試各種不同的算法在各種數(shù)據(jù)情況下的表現(xiàn)。各組測試數(shù)據(jù)特點如下：

• 數(shù)據(jù)1：與樣例等價，測試基本正確性；
• 數(shù)據(jù)2：102個隨機整數(shù)；
• 數(shù)據(jù)3：103個隨機整數(shù)；
• 數(shù)據(jù)4：104個隨機整數(shù)；
• 數(shù)據(jù)5：105個隨機整數(shù)；

輸入格式:

輸入第1行給出正整數(shù)K?(≤)；第2行給出K個整數(shù)，其間以空格分隔。

輸出格式:

在一行中輸出最大子列和。如果序列中所有整數(shù)皆為負數(shù)，則輸出0。

輸入樣例:

6 -2 11 -4 13 -5 -2

輸出樣例:

20

提交代碼 #include <stdio.h> #include <stdlib.h> #include <string.h>#define MIN_VAL -2147483648void solve_1_o_n2() {int n;scanf("%d",&n);int *arr = (int *)malloc(sizeof(int)*n);int sumlr = 0;int tmp = 0;bool allNeg = true;for(int i=0;i<n;i++){scanf("%d",&tmp);if(tmp>=0 && allNeg){allNeg = false;}sumlr += tmp;arr[i] = sumlr;}if(allNeg){printf("0\n");}else{int maxval = MIN_VAL;for(int i=0;i<n-1;i++){for(int j=i+1;j<n;j++){if(arr[j]-arr[i]>maxval){maxval = arr[j]-arr[i];}}}for(int i=0;i<n;i++){maxval = maxval<arr[i]?arr[i]:maxval;}printf("%d\n",maxval);}free(arr); }void solve_2_o_n() {int n;scanf("%d",&n);int *arr = (int *)malloc(sizeof(int)*(n+1));memset(arr,0,sizeof(int)*(n+1));int maxval = MIN_VAL;bool allNeg = true;for(int i=1;i<=n;i++){scanf("%d",arr+i);if(arr[i]>=0 && allNeg)allNeg = false;}if(allNeg){printf("0\n");}else{for(int i=1;i<=n;i++){if(arr[i-1]>=0){arr[i] += arr[i-1];maxval = arr[i] > maxval ? arr[i] : maxval;}}printf("%d\n",maxval);}free(arr); }void solve_3_best() {int n;int lastSum=0,thisNum=0;int maxVal = MIN_VAL;bool allNeg = true;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&thisNum);if(thisNum>=0 && allNeg)allNeg = false;if(lastSum>=0){thisNum += lastSum;if(thisNum>maxVal)maxVal = thisNum;}lastSum = thisNum;}printf("%d\n",allNeg?0:maxVal); }int main() { // solve_1_o_n2(); // solve_2_o_n(); solve_3_best();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cbattle/p/10757095.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的7-1 最大子列和问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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