3487. Maximum Unique Subarray Sum After Deletion
Approach
If no duplicates, sum all positives; else take max element + all unique positives.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
// Approach: If no duplicates, sum all positives; else take max element + all unique positives.
// Time: O(n) Space: O(n)
public class Solution
{
public int MaxSum(int[] nums)
{
// Find the maximum value in the array
int max = nums.Max();
// If the maximum value is less than or equal to 0, return it
if (max <= 0)
return max;
// Boolean array to keep track of numbers that have been added to the sum
bool[] seen = new bool[201]; // Assuming numbers are within the range of 0 to 200
int result = 0; // Initialize the sum
// Iterate through each number in the array
foreach (int num in nums)
{
// If the number is negative or has already been added, skip it
if (num < 0 || seen[num])
continue;
// Add the number to the sum and mark it as seen
result += num;
seen[num] = true;
}
// Return the calculated sum
return result;
}
}