美文网首页
一维数组,求最大子串和

一维数组,求最大子串和

作者: 贰拾贰画生 | 来源:发表于2017-10-13 00:03 被阅读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;
    }
    
    
    
    
    

    相关文章

      网友评论

          本文标题:一维数组,求最大子串和

          本文链接:https://www.haomeiwen.com/subject/jnsayxtx.html