算法介紹

算法一：暴力法

不同的是并沒(méi)有使用三重循環(huán)來(lái)進(jìn)行遍歷棺聊，因?yàn)橛^察到每一次只需要在a[i]后加一個(gè)即可侯养，所以時(shí)間復(fù)雜度為O(n^2)拍鲤。

#include <stdio.h>
#include <stdlib.h>

int main()
{
  int k = 0;
  scanf("%d", &k);
  int *a = (int*)malloc(sizeof(int) * k);
  for(int i = 0; i < k; i++){
    scanf("%d", &a[I]);
  }
  int maxsum = 0;
  for(int i = 0; i < k; i++){
    int thissum = 0;
    for(int j = i; j < k; j++){
        thissum += a[j];
        if(thissum > maxsum){
          maxsum = thissum;
        }
    }
  }
  free(a);

  if(maxsum > 0){
    printf("%d", maxsum);
  }
  else{
    printf("0");
  }
  return 0;
}

算法二：在線處理法

在線處理法就是在輸入的時(shí)候進(jìn)行條件的判斷，有點(diǎn)像對(duì)每一個(gè)數(shù)進(jìn)行實(shí)時(shí)處理憋沿，在輸入完成后結(jié)果也就得出旺芽，所以時(shí)間復(fù)雜度最低，為O(N)辐啄。具體的判斷條件是如果輸入的數(shù)加上目前的序列和之后導(dǎo)致了當(dāng)前序列和的減少甥绿，則不進(jìn)行錄入，當(dāng)相加后當(dāng)前序列和小于0時(shí)则披，則放棄該序列，因?yàn)橹粫?huì)對(duì)之后的序列和產(chǎn)生副作用洗出。缺點(diǎn)是不是很直觀地讓人理解士复。

#include <stdio.h>

int main()
{
  int k = 0, x = 0;
  scanf("%d", &k);
  int  thissum = 0, maxsum = 0;
  for(int i = 0; i < k; i++){
    scanf("%d", &x);
    thissum += x;
    if(thissum > maxsum){
      maxsum = thissum;
    }
    else if(thissum < 0){
      thissum = 0;
    }
  }
  if(maxsum > 0){
    printf("%d", maxsum);
  }
  else{
    printf("0");
  }
  return 0;
}

算法三：分治法

這個(gè)方法較為復(fù)雜，就我個(gè)人而言理解和實(shí)現(xiàn)起來(lái)都比在線處理法麻煩不少，具體實(shí)現(xiàn)思路就是將一個(gè)規(guī)模比較大的問(wèn)題通過(guò)不斷劃分劃分成一個(gè)個(gè)小規(guī)模的問(wèn)題阱洪，然后再將每個(gè)小問(wèn)題的解集中起來(lái)便贵，通過(guò)考慮到跨越邊界的情況最終得出答案。（真是又復(fù)雜又難敲）
貼一個(gè)圖幫助理解一下：

分治法

#include <stdio.h>

int Max3(int A, int B, int C){
    //返回3個(gè)整數(shù)中的最大值
    return A > B ? A > C ? A : C : B > C ? B : C;
    //return A > B ? (A > C ? A : (B > C ? B : C)) : B > C ? B : C;
}

int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子問(wèn)題的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界線的結(jié)果*/
 
    int LeftBorderSum, RightBorderSum;
    int center, i;
 
    if( left == right )  { /* 遞歸的終止條件冗荸，子列只有1個(gè)數(shù)字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }
 
    /* 下面是"分"的過(guò)程 */
    center = ( left + right ) / 2; /* 找到中分點(diǎn) */
    /* 遞歸求得兩邊子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );
 
    /* 下面求跨分界線的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 從中線向左掃描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左邊掃描結(jié)束 */
 
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 從中線向右掃描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右邊掃描結(jié)束 */
 
    /* 下面返回"治"的結(jié)果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
 
int MaxSubseqSum3( int List[], int N )
{ /* 保持與前2種算法相同的函數(shù)接口 */
    return DivideAndConquer( List, 0, N-1 );
}

int main()
{
    int k = 0;
    scanf("%d", &k);
    int a[k];
    for(int i = 0; i < k; i++){
        scanf("%d", &a[i]);
    }

    int res = MaxSubseqSum3(a, k);
    printf("%d", res);
    return 0;

}

不過(guò)這代碼看著工整舒服承璃，遞歸還是沒(méi)有明白。

練習(xí)：

題目網(wǎng)站：https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

題目描述：

1007 Maximum Subsequence Sum （25 point(s)）
Given a sequence of K integers { N?1?? , N?2, ..., N?K}. A continuous subsequence is defined to be { N?I, N?I+1, ..., Nj} where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

易錯(cuò)點(diǎn)分析

本題唯一的會(huì)影響AC的就是對(duì)于輸出格式的要求蚌本， 一開(kāi)始以為是輸出對(duì)應(yīng)的起止數(shù)據(jù)的下標(biāo)盔粹，后來(lái)發(fā)現(xiàn)是輸出對(duì)應(yīng)的數(shù)，所以說(shuō)樣例還是很有誤導(dǎo)性的程癌，如果沒(méi)有完全看清楚題目要求很容易在這卡住舷嗡，只會(huì)得個(gè)辛苦分3分，出題的果然都想好了情況嵌莉。對(duì)于輸出的要求分為以下幾種：
1.存在最大子序列进萄，則輸出max_sum以及對(duì)應(yīng)的起止數(shù)據(jù)（如果最后一位是0的話，也要將0算進(jìn)最大子序列中）锐峭；
2.不存在最大子序列中鼠，輸出0和輸入的首尾數(shù)據(jù)；
3.輸入全為負(fù)數(shù)沿癞，輸出0和輸入的首位數(shù)據(jù)援雇；
4.輸入全為負(fù)數(shù)和0，負(fù)數(shù)全部算作0抛寝，輸出三個(gè)0.
這里面最后一個(gè)條件比較難以發(fā)現(xiàn)熊杨，同時(shí)也要注意與第三中情況區(qū)分開(kāi)。

思路分析

下午剛學(xué)的方法就可以用盗舰，所以這道題最起碼有三種解法晶府，也就是上面的三種算法。
首先是在線處理法钻趋，我實(shí)現(xiàn)輸出的思路是對(duì)最后符合要求的那個(gè)i記為z川陆，說(shuō)明到這結(jié)束，如果this_sum > max_sum蛮位， 則较沪，z更新，同時(shí)子序列長(zhǎng)度count++失仁，最終只要將z減去長(zhǎng)度再加一即可得到子序列首位的數(shù)據(jù)尸曼。如果是使用暴力法的話，就直接將q = i, z = j萄焦，不斷更新即可控轿，不再詳細(xì)說(shuō)明冤竹。實(shí)現(xiàn)思路上肯定是前者較為復(fù)雜，但是算法效率毋庸置疑是前者茬射。

在線處理法：
#include <stdio.h>

int main()
{
    int k = 10, x = 0;
    scanf("%d", &k);
  //int a[] = {-10, 1, 2, 3, 4, 1, -23, 2, 7, -21};
  int a[k];
    int this_sum = 0, max_sum = 0, q = 0, z = 0, count  = 0, ret = 0, fu = 0, zero = 0;
  for(int i = 0; i < k; i++){
    scanf("%d", &a[i]);
    if(a[i] == 0){
      zero++;
    }
    if(a[i] < 0){
      fu++;
    }
  }
  if(fu+zero == k && zero != 0){
    printf("0 0 0");
  }
  else if(fu == k){
    printf("0 %d %d", a[0], a[k-1]);
  }
  else{
    for(int i = 0; i < k; i++){
      this_sum += a[i];
      count++;
      if(this_sum > max_sum){
        max_sum = this_sum;
        z = i;
        ret = 1;    
      }
      if(ret){
        q = z - count+1;
        }
      if(this_sum < 0){
        this_sum = 0; 
        count = 0;
      }
      ret = 0;
    }
    if(max_sum <= 0){
      printf("0 %d %d", a[0], a[k-1]);
    }
    else{
      printf("%d %d %d", max_sum, a[q], a[z]);
    }
  }
    return 0;
}

暴力法（直接搬運(yùn)https://blog.csdn.net/wwk0125/article/details/50444529）
#include<iostream>
#include<cstdio>
using namespace std;
#define maxN 10001
#define Inf 0x3f3f3f
 
int main()
{   
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int a[maxN];
    int k,sum,max=-Inf;
    int L, R;
    cin >> k;
    for (int i = 0; i < k; i++)
        cin >> a[i];
 
    
    for (int i = 0; i < k; i++)
    {
        sum = 0;
        for (int j = i; j < k; j++)
        {
            sum += a[j];
                if (sum>max)
                {
                    max = sum;
                    L = i;
                    R = j;
                }
        }
    }
    if (max<0)  //全為負(fù)數(shù)時(shí),按=0處理鹦蠕，輸出頭尾
        cout << "0" << " " << a[0] << " " << a[k-1] << endl;
    else
    cout << max << " " <<a[L] << " " << a[R] << endl;
    return 0;
}
/*
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
*/

原本以為暴力法會(huì)有一個(gè)點(diǎn)超時(shí)，結(jié)果沒(méi)有在抛，早知道就直接暴力了钟病。