阿里后端开发岗java 0424第一题题解 dp动归

package com.Alibaba.exam0424;

public class Main3 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n=6;
        int m=11;
        int[] arr= {4,12,3,7,6,2};    
        int[][] dp=new int[n][m];//m表示m种评价标准，0到m-1
        int tmp=arr[0]%m;
        for(int k=tmp;k<m;k++) {
        	dp[0][k]=tmp;//初始化
        }

        for(int i=1;i<n;i++) {
        	for(int j=0;j<m;j++) { 
        		int col=(j-arr[i])%m;
        		while(col<0) {
        			col+=m;
        			//col%=m;
        		}
        		int tmp2=Math.max(dp[i-1][j], (dp[i-1][col]+arr[i])%m);
                        dp[i][j]=Math.max(dp[i][j], tmp2);
        	}       	
        }
        System.out.println(dp[n-1][m-1]);
	}

}