3068. Find the Maximum Sum of Node Values

HardView on LeetCode

Array Dynamic Programming Greedy Tree Depth-First Search

Time: O(n)

Space: O(1)

Intuition

Find maximum sum by selecting elements such that no element is divisible by the previous. Greedy or DP.

Algorithm

1Sort descending. Greedy: take element if not divisible by the last taken.

Common Pitfalls

•The constraint is on consecutive selected elements. Greedy after sorting.

3068.cs

// Approach: XOR each element if gain > 0; must XOR even count; adjust for minimum loss if odd.
// Time: O(n) Space: O(1)

public class Solution
{
    public long MaximumValueSum(int[] nums, int k, int[][] edges)
    {
        long sum = 0, cnt = 0, minChangedDiff = Int32.MaxValue;

        foreach (int el in nums)
        {
            sum += Math.Max(el, el ^ k);
            cnt += ((el ^ k) > el) ? 1 : 0;
            minChangedDiff = Math.Min(minChangedDiff, Math.Abs(el - (el ^ k)));
        }

        if (cnt % 2 == 0)
            return sum;

        return sum - minChangedDiff;
    }
}

Was this solution helpful?