DDSA Solutions

3068. Find the Maximum Sum of Node Values

HardView on LeetCode
ArrayDynamic ProgrammingGreedyTreeDepth-First Search
Time: O(n)
Space: O(1)

Problem Overview

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

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems