二叉树中的最大路径和

C 解法, 执行用时: 2ms, 内存消耗: 340KB, 提交时间: 2022-03-12

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int max(int a,int b){
	return a>b?a:b;
}

int main(){
	
	int mm = INT_MIN;
	int m;
	scanf("%d",&m);
	int a[m],fnode[m];
	int i,j;
	int n,cnt1,cnt2 ;
    int val=mm;
	int dp[m][3];
	for(i=0;i<m;i++){
		for(j=0;j<3;j++){
			dp[i][j]=mm;
		}
	}
	for(i=0;i<m;i++){
		scanf("%d",a+i);
		dp[i][0] = a[i];
	}
	for(i=0;i<m;i++){
		scanf("%d",fnode+i);
	}
	
	for(i=m-1;i>=0;i--){
		j=i;
		n=fnode[j];
     //   val=max(val,dp[j][0]);
        
		cnt1= max(0,dp[j][1]);
		cnt2=max(0,dp[j][2]);
		val=max(val,max(dp[j][0]+cnt1+cnt2,max(cnt1,cnt2)));
		if(n==0) break; 
		cnt1=max(cnt1,cnt2)+dp[j][0];
		if(dp[n-1][1]<0){
			dp[n-1][1]=max(0,cnt1);
		
		}else{
			dp[n-1][2]=max(0,cnt1);
		}
		
	}
	

    if(m==1){
        printf("%d",a[0]);
    }else{
        printf("%d",val);
    }
	//printf("%d",val);
	
	return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 348KB, 提交时间: 2022-05-08

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int u = INT_MIN;
    int m;
    scanf("%d", &m);
    int a[m], fnode[m];
    int i, j;
    int n, x, y;
    int v = u;
    int dp[m][3];
    for (i = 0; i < m; i++) {
        for (j = 0; j < 3; j++) {
            dp[i][j] = u;
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d", a + i);
        dp[i][0] = a[i];
    }
    for (i = 0; i < m; i++) {
        scanf("%d", fnode + i);
    }
    for (i = m - 1; i >= 0; i--) {
        j = i;
        n = fnode[j];
        x = max(0, dp[j][1]);
        y = max(0, dp[j][2]);
        v = max(v, max(dp[j][0] + x + y, max(x, y)));
        if (n == 0) break;
        x = max(x, y) + dp[j][0];
        if (dp[n - 1][1] < 0) {
            dp[n - 1][1] = max(0, x);
        } else {
            dp[n - 1][2] = max(0, x);
        }
    }
    if (m == 1) {
        printf("%d", a[0]);
    } else {
        printf("%d", v);
    }
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 404KB, 提交时间: 2022-08-06

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main(){
    int mm=INT_MIN;
    int m;
    scanf("%d",&m);
    int a[m],fnode[m];
    int i,j;
    int n,cnt1,cnt2;
    int val=mm;
    int dp[m][3];
    for(i=0;i<m;i++)
    {
        for(j=0;j<3;j++)
        {
            dp[i][j]=mm;
        }
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",a+i);
        dp[i][0]=a[i];
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",fnode+i);
    }
    for(i=m-1;i>=0;i--)
    {
        j=i;
        n=fnode[j];
        cnt1=max(0,dp[j][1]);
        cnt2=max(0,dp[j][2]);
        val=max(val,max(dp[j][0]+cnt1+cnt2,max(cnt1,cnt2)));
        if(n==0) break;
        cnt1=max(cnt1,cnt2)+dp[j][0];
        if(dp[n-1][1]<0)
        {
            dp[n-1][1]=max(0,cnt1);
        }else{
            dp[n-1][2]=max(0,cnt1);
        }
    }
    if(m==1)
    {
        printf("%d",a[0]);
    }else{
        printf("%d",val);
    }
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-05-08

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int u = INT_MIN;
    int m;
    scanf("%d", &m);
    int a[m], fnode[m];
    int i, j;
    int n, x, y;
    int v = u;
    int dp[m][3];
    for (i = 0; i < m; i++) {
        for (j = 0; j < 3; j++) {
            dp[i][j] = u;
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d", a + i);
        dp[i][0] = a[i];
    }
    for (i = 0; i < m; i++) {
        scanf("%d", fnode + i);
    }
    for (i = m - 1; i >= 0; i--) {
        j = i;
        n = fnode[j];
        x = max(0, dp[j][1]);
        y = max(0, dp[j][2]);
        v = max(v, max(dp[j][0] + x + y, max(x, y)));
        if (n == 0) break;
        x = max(x, y) + dp[j][0];
        if (dp[n - 1][1] < 0) {
            dp[n - 1][1] = max(0, x);
        } else {
            dp[n - 1][2] = max(0, x);
        }
    }
    if (m == 1) {
        printf("%d", a[0]);
    } else {
        printf("%d", v);
    }
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-03-06

#include<bits/stdc++.h>
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
    Node(int _v):val(_v),left(nullptr),right(nullptr){}
};
int res = INT_MIN;
int fun(Node* root){
    if(!root) return 0;
    int left = max(fun(root -> left),0);
    int right = max(fun(root -> right),0);
    res = max(res,left + right + root -> val);
    return max(root -> val + left,root -> val + right);
    
}
int main(){
    int n ;
    cin >> n;
    int value;
    vector<Node*> node;
    for( int i = 0; i < n; i++){
        
        cin >> value;
        auto temp = new Node(value);
        node.push_back(temp);
    }
    Node* root;
    for( int i = 0; i < n; i++){
        cin >> value;
        if(value == 0){
            root = node[i];
            continue;
        }
        if(! node[value - 1] -> left){
            node[value - 1] -> left = node[i];
        }else{
            node[value - 1] -> right = node[i];
        }
    }
    fun(root);
    cout<<  res;
    return 0;
    
}

详情