动态规划——最大子串和

在学生年代的时候，有一段时间爱好刷水题，还狂言说每天要刷一道，但是技术不精，遇到困难就退缩了，后来有一次去腾讯面试的时候问到敏感词过滤算法怎么实现，当然了，今天要说的不是这个，这个太难了，就是我参加工作有大半年了，也无法参透这个高深的问题。所以学习算法还是很有必要的。

描述
给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1<=x<=y<=n。
输入
第一行是一个整数N(N<=10)表示测试数据的组数）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000)
输出
对于每组测试数据输出和最大的连续子串的和。
样例输入

1
5
1 2 -1 3 -2

样例输出

5

提示
输入数据很多,推荐使用scanf进行输入

这个题相信很多人看到的时候都会瞬间懵逼，最简单的想法就是直接for循环，把每一个子串的和都算出来，这样子无疑是效率最低的方法了。我们考虑算法的时候不应该只注意到元素个体本身，还要关注到元素的属性，我觉得这一题的关键点就在这里。数字本身的一个属性正数+负数肯定小于正数本身，所以我们对数组进行一次遍历，假设第一个值为最大子串和，比如上面的例子

Paste_Image.png

1、第1个数据和第2个数据相加为3，当前最大子串和为3
2、继续往后相加，加上第3个数后为2，当前子串相加值依然大于0
3、继续往后相加，加上第4个数后为5，当前最大子串和为5
4、继续往后相加，加上第5个数后为3，最大子串和为5
Java实现

    private static int maxSum(int[] num){
        int result = num[0];
        int maxResult = num[0];
        for (int i = 1; i < num.length; i++) {
            result += num[i];
                // 相加之后大于结果值，注意需要考虑全是负数的情况
                if (result > maxResult) {
                    // 比较是否大于最大值maxResult
                        maxResult = result;
                }else {
                    if (result < 0) {
                        // 否则如果相加的结果小于0，并且小于maxResult，这个子串的最大值就确定下来了
                        result = 0;//重置 
                    }
                }
        }
        return maxResult;
    }

C++实现

#include <iostream>
using namespace std;

int maxSum(int *num,int size){
    int result = num[0];
    int maxResult = num[0];
    for (int i = 1; i < size; i++) {
        result += num[i];
        if (result > maxResult) {
             maxResult = result;
        }else {
           if(result < 0){
               result = 0;         
            }
        }
     }
      return maxResult;
}

int main(){
      int n,group;
      cin>>n;
      int *groups = new int[n];
      for(int i=0;i<n;i++){
            cin>> group;
            int *num = new int[group];
            for(int j=0;j<group;j++){
                  cin>>num[j];
            }
            groups[i] = maxSum(num,group);
            delete []num;
      }
      for(int i = 0;i<n;i++)
            cout<<groups[i]<<" ";
      delete []groups;
      return -1; 
}

最后我们来看看两种语言的效率问题，可以明显看到C++的速度远远快过Java，咱们以后还是多多学习C++吧