一维数组,求最大子串和

2017-10-13  本文已影响16人  贰拾贰画生

这个题其实是比较简单的,但是要注意的一点是要能处理全负数的情况,老是忘,今天做个记录:

#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>
#include <string>
#include <sstream>
#include <queue>
//#include <hash_map>

using namespace std;

int main(){

    int a[8] = {-1, -2, -3, -10, -4, -7, -2, -5};
    int res = a[0];
    int minS = a[0];
    int sum = a[0];
    for (int i = 1; i < 8; ++i) {
        // 下边三行的顺序很重要,不能换
        sum += a[i];
        res = max(res, sum - minS);
        minS = min(minS, sum);
    }
    cout<< res<< endl;
    
    
    return 0;
}




上一篇 下一篇

猜你喜欢

热点阅读