美团2018： 给出一个数组序列和一个sum，求出该数组 子数组（必须连续）和为sum的最大长度 解法一：这是我用动态规划方法写的代码；空间，时间复杂度都很高
private static int process(int[] nums,int n,int k) { int max = 0; int []sum=new int[n+1]; int [][]dp=new int[n+1][n+1]; //初始化 for(int j=1;j<n+1;j++){ sum[j]=sum[j-1]+nums[j-1];//sum[0]=0; sum[1]=num[0]; sum[2]=num[0]+nums[1]//sum数组的坐标为长度 if(sum[j]%k==0){ dp[0][j]=j; //记下最大值 if(dp[0][j]>max){ max=dp[0][j]; } }else{ dp[0][j]=dp[0][j-1]; } } for(int i=1;i<n+1;i++){ for(int j=i;j<n+1;j++){ int tempsum=sum[j]-sum[i]+nums[i-1];//i - j的和 if(tempsum%k==0){ dp[i][j]=j-i+1; //记下最大值 if(dp[i][j]>max){ max=dp[i][j]; } }else{ int tempmax=Math.max(dp[i-1][j], dp[i][j-1]); int temp=Math.max(tempmax, dp[i-1][j-1]); dp[i][j]=temp; //记下最大值 if(dp[i][j]>max){ max=dp[i][j]; } } } } return max; }解法二：空间复杂度O(n)解法
private static int resolve(int[] nums,int n,int k) { int max = 0; for(int i=0;i<n-max;i++){ int res = nums[i]; if(max==0&&nums[i]%k==0&&nums[i]!=0) max=1; for(int j=i+1;j<n;j++){ res+= nums[j]; if(res!=0&&res%k==0&&max<(j-i+1)) max=j-i+1; } } return max; }