一个一维维数组中只有1和-1，实现程序，求和为0的最长子串长

def foo(arr):
    dp = [0] * (len(arr) + 1)
    dp[0] = 0
    dp[1] = 0
    for i in range(1, len(arr)):
        if arr[i] == -arr[i-1]:
            dp[i+1] = dp[i-1] + 2
        elif arr[i] == -arr[i-dp[i]-1]:
            dp[i+1] = dp[i] + 2
        else:
            dp[i+1] = 0
    print(dp)
    return max(dp)

foo([ -1, -1,-1, -1, -1, 1, 1, 1])
>>> 6
foo([-1, 1, -1, -1, 1, -1])
>>> 4

public class Solution {
    public static int getLongestLength(List<Integer> array) {
        if(array.size() <= 1)
            return 0;
        int max = 0;
        int size = array.size();
        //tab[i][j]表示从array[i]一直加到array[j]的和
        int[][] tab = new int[size][size];

        //求两两相邻的和，作为下一步的边界条件
        for(int i = 1; i < size; i++) {
            tab[i-1][i] = array.get(i-1) + array.get(i);
            if(array.get(i) == -array.get(i-1)) 
                max = 2;
        }

        //由于数组中只有1和-1，要使结果为0，子串长度必须为偶数，因此len = len + 2;
        for(int len = 3; len < size; len = len + 2) {
            for(int i = 0, j; (j = i + len) < size; i++) {
                tab[i][j] = array.get(i) + array.get(j) + tab[i + 1][j - 1];
                if(tab[i][j] == 0) {
                    max = Math.max(max, j-i+1);
                }
            }
        }
        return max;
    }
} 

// Java
int getLongestLength(List<Integer> array){
    //  动规，leetcode32最长有效括号变体
    // 时间复杂度 O(N)
    // 空间复杂度 O(N)
    int len = array.length();
    int[] nums = new int[len];
    int[] dp = new int[len];
    nums[0] = array.get(0);
    int res = 0;
    for(int i = 1; i < len; i++) {
        nums[i] = array.get(i);
        if(nums[i] + nums[i-1] == 0) {
            dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
        } else if(i - dp[i-1] > 0 && nums[i-dp[i-1]-1] + nums[i] == 0) {
            dp[i] = (i-dp[i-1] >= 2 ? dp[i-dp[i-1]-2] : 0) + 2 + dp[i-1];
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

public class Solution {

    public static void main(String[] args) {
        int[] nums={1,1,1,1,-1,-1,-1,-1,1,1,1};
        System.out.println(getLongest(nums));
    }

    

    //最长为0的子串
    public static int getLongest(int[] nums)
    {
        //动态规划
        int begin=0;
        int maxLength=0;
        //扩大规则  dp[i][j]=dp[i+1][j-1]+nums[i]+nums[j]
        int length=nums.length;
        int[][] dp=new int[length][length];

        //一个数
        for(int i=0;i<length;i++)
            dp[i][i]=nums[i];

        for(int j=1;j<length;j++)
            for(int i=0;i<j;i++)
            {
                //两个数
                if(j-i==1)
                    dp[i][j]=nums[i]+nums[j];
                else//大于两个数
                    dp[i][j]=nums[i]+nums[j]+dp[i+1][j-1];


                if(dp[i][j]==0)
                    maxLength=Math.max(maxLength,j-i+1);
            }
        return maxLength;
    }

}

思路如下：直接遍历数组，记录数组中1和-1的个数，最长的字串长度即为个数较少的那个数的2倍；

class Solution(object):
    def fun(self,l):
        p=0
        t=0
        for i in range(len(l)):
            if l[i]>0:
                p+=1
            else:
                t+=1
        result=2*min(t,p)
        print(result)
        return result