劍指OFFER之最大子向量和（連續子數組的最大和）（九度OJ1372）

題目描述：

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天JOBDU測試組開完會後,他又發話了:在古老的一維模式識別中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,並期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠住？

 

輸入：

輸入有多組數據,每組測試數據包括兩行。

第一行為一個整數n(0<=n<=100000),當n=0時,輸入結束。接下去的一行包含n個整數(我們保證所有整數屬於[-1000,1000])。

 

 

 

 

輸出：

對應每個測試案例,需要輸出3個整數單獨一行,分別表示連續子向量的最大和、該子向量的第一個元素的下標和最後一個元素的下標。若是存在多個子向量,則輸出起始元素下標最小的那個。

 

樣例輸入：

3
-1 -3 -2
5
-8 3 2 0 5
8
6 -3 -2 7 -15 1 2 2
0

樣例輸出：

-1 0 0
10 1 4
8 0 3

解題思路：

　　算法思路，大概是：

　　我們記錄當前掃描的最大和，與記錄中的最大和。如果當前的和超過了最大和，就替換，並且記錄兩端坐標。否則就繼續掃描。

while(i<n){
            if(newMax < 0){
                newMax = gArr[i];
                newBegin = i;
                newEnd = i;
            }else{
                newMax += gArr[i];
                newEnd = i;
            }
            if(newMax > realMax){
                realMax = newMax;
                realBegin = newBegin;
                realEnd = newEnd;
                flag = 1;
            }
            i++;
        }

　　但是，這個題目的測試用例很奇怪，它僅支持前向的最大子段，而不是後向的最大字段。舉個例子：

　　我們輸入-1 0 5 0 0 得到的應該是5 1 2  而不是5 1 4，也就是說，它向前滿足最大子段，但是不保證向後滿足，但是也可能是沒有這種用例，我的代碼剛好踩中了空擋區。至少我的通過用例是這樣證明的。如果理解不對，還請改正。第二個測試用例很奇怪。

全部代碼：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100000
int gArr[MAXSIZE] = {0};
int main(){
    int n,i;
    int realMax,realBegin,realEnd;
    int newMax,newBegin,newEnd;
    int flag;
    while(scanf("%d",&n)!=EOF && n>0 && n <= 100000){
        for(i=0;i<n;i++){
            scanf("%d",&gArr[i]);
        }
        realMax=-1001,realBegin=0,realEnd=0;
        newMax=-1001,newBegin=0,newEnd=0;
        flag = 0;
        i=0;
        while(i<n){
            if(newMax < 0){
                newMax = gArr[i];
                newBegin = i;
                newEnd = i;
            }else{
                newMax += gArr[i];
                newEnd = i;
            }
            if(newMax > realMax){
                realMax = newMax;
                realBegin = newBegin;
                realEnd = newEnd;
                flag = 1;
            }
            i++;
        }
        if(flag)
            printf("%d %d %d\n",realMax,realBegin,realEnd);
        else
            printf("%d %d %d\n",-1,0,0);
    }
    return 0;
}
/**************************************************************
    Problem: 1372
    User: xhalo
    Language: C
    Result: Accepted
    Time:450 ms
    Memory:1304 kb
****************************************************************/