狗家电面

求问楼主可以给个例子吗？难道不是求maximum sum of the connected component吗？

[1, 3, 4, 5, 0, 0]
[2, 0, 0, 7, 0, 1]
[1, 0, 2, 9, 9, 2]
[1, 0, 6, 0, 7, 0]
求全部联通的和好像不太对，因为每个点只能访问一遍，上图如果走到最下面一行的6或者7以后就没有办法出来了。
是不是应该以每个非0点作为起点，DFS所有可能的最大值。
时间复杂度太高了。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

请问楼主是不是应该这样的？

1. public static void main(String[] args) {
   
2.                 // TODO Auto-generated method stub
   
3.                 int[][] arr = new int[][]{{8,0,0,5},
   
4.                                                                   {1,8,0,3},
   
5.                                                                   {6,0,1,10},
   
6.                                                                   {3,2,0,4}};
   
7.                 System.out.println(maxPathSum(arr));                                                 
   
8.         }
   
9.        
   
10.         public static int maxPathSum(int[][] arr) {
    
11.                 int res = 0;
    
12.                 for (int i = 0; i < arr.length; i++) {
    
13.                         for (int j = 0; j < arr.length; j++) {
    
14.                                 if (arr[i][j] != 0)
    
15.                                         res = Math.max(res, dfs(arr, i, j, 0));
    
16.                         }
    
17.                 }
    
18.                 return res;
    
19.         }
    
20.        
    
21.         public static int dfs(int[][] arr, int x, int y, int sum) {
    
22.                 if (x < 0 || y < 0 || x >= arr.length || y >= arr[0].length || arr[x][y] == 0)
    
23.                         return sum;
    
24.                 int val = arr[x][y];
    
25.                 sum += val;
    
26.                 arr[x][y] = 0;
    
27.                 int left = dfs(arr, x, y - 1, sum);
    
28.                 int right = dfs(arr, x, y + 1, sum);
    
29.                 int up = dfs(arr, x - 1, y, sum);
    
30.                 int down = dfs(arr, x + 1, y, sum);
    
31.                 arr[x][y] = val;
    
32.                 return Math.max(left, Math.max(right, Math.max(up, down)));
    
33.         }
    
34.        

复制代码

ysboss123 发表于 2019-9-27 09:50
请问楼主是不是应该这样的？
[mw_shl_code=java,true]public static void main(String[] args) {
                // T ...

第一次贴代码，格式乱了，尴尬。。。

两次DFS？

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies