求和为0的最长连续子序列长度

 

题意：给定一个数组，数组中元素的值只能是1或者-1，求其和为0的最长连续子序列的长度；

　　　　数组为1，-1，1，-1，1，-1，1，-1，其结果为：8

　　　　数组为1，1，-1，1，1，-1，-1，其结果为：6

解析：

　　通过分析可知，要使其和为0，只有当1和-1的个数相等时，才会成立，但题目要求是连续子序列，所以单纯统计其1和-1个数不可取。

　　由题目中求最长连续子序列，可想到动态规划来求解，动态规划的求解既是寻找其状态转移方程和建立状态转移表的过程

　　设dp[i]为下标为i及其之前数组中所有元素的和，

　　                                             

 

   
 

如图所示，数组为1，-1，1，-1，1，-1，1，-1最后一个值为0，直接满足结果，输出8

如上图，数组1，1，-1，1，1，-1，-1，dp取值为dp[0] = dp[2] = dp[6] = 1; dp[1] = dp[3] = d[5] = 3; dp[4] = 3;

对于每个值，取最后一次出现的位置和第一次出现的位置之差，取它们的最大值，max((6 - 0),(5 - 1),(4 - 4) = 6

代码如下所示：

#include <cstdio>
#include <map>
#include <vector>
#include <iostream>
#include <cstdlib>

using namespace std; 

int main()
{
    int n,val;
    while (cin >> n) {
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> val;
            arr[i] = val;
        }
        vector<int> dp(n + 1);
        dp[1] = arr[1];
        for (int i = 2; i <= n; i++)
            dp[i] = arr[i] + dp[i - 1];

        //求取dp[i] = dp[j],i表示dp[i]的值第一次出现的位置，j表示其最后一次出现的位置
        //for (const auto &s : dp)
        //    cout << s << " ";
        //cout << endl;
        map<int, int> m;
        int begin, max = 0;
        for (int i = 1; i <= n; i++) {
            begin = m[dp[i]];
            if (begin == 0 && dp[i] != 0) {
                m[dp[i]] = i;
            }
            else {
                if (i - begin > max) {
                    max = i - begin;
                }
            }
        }
        cout << max << endl;
    }
    system("pause");
    return 0;
}