Help me with this question
Can I get the confirmation that it is not from an ongoing contest because I am not allowed to help with that?
No ,It is just mock interview sample given in Hackerearth and it is ended then I have posted doubt.
Okay, thanks!!
Note that this is the same as performing Kadane’s Algorithm while descending down during a DFS.
So while doing the normal DFS, do something similar to Kadane’s and store the answer for each node.
If you have a link to the question, I might send you the exact code.
I tried the same but unable to implement
Is the question publicly available?
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int A[N], ans[N];
vector<int> adj[N];
void dfs(int node, int parent, int csum, int cmax) {
csum = max(0, csum + A[node]);
cmax = max(cmax, csum);
ans[node] = cmax;
for (int child : adj[node]) {
if (child != parent) {
dfs(child, node, csum, cmax);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> A[i];
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0, 0, 0);
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
return 0;
}
Your code is failing many test cases,mock interview of Hackerearth has shuffled questions ,so it may happen you won’t find this one
Okay, I think it is because they want you to compulsorily choose at least one vertex. That is, it is not necessary that answer is always >= 0.
You’ll then have to modify the Kadane algorithm as done for case when all values are negative.
I’ll post the modified code.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 1e9 + 100;
int A[N], ans[N];
vector<int> adj[N];
void dfs(int node, int parent, int max_ending_here, int max_so_far, int max_element) {
max_ending_here = max(0, max_ending_here + A[node]);
max_so_far = max(max_so_far, max_ending_here);
max_element = max(max_element, A[node]);
if (max_so_far == 0) { max_so_far = max_element; }
ans[node] = max_so_far;
for (int child : adj[node]) {
if (child != parent) {
dfs(child, node, max_ending_here, max_so_far, max_element);
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> A[i];
}
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0, 0, -INF, -INF);
for (int i = 1; i <= n; ++i) {
cout << ans[i] << ' ';
}
return 0;
}
I didn’t understand.plz explain using some example
If you understood the previous, then this is just the extension of kadane for the case when all numbers are negative.
You can also read about this here, https://stackoverflow.com/a/9942496/6663620.