Largest Sum Contiguous Subarray and Sum of Prime Factors
Filed under Adobe
Free read 2 of 3Understand whether prime factor sum includes duplicate prime factors or distinct ones.
The question
Find the largest sum contiguous subarray (Kadane's Algorithm) and calculate the sum of distinct prime factors of a given number.
Constraints
- 1 <= n <= 10^5 for array
- 2 <= number <= 10^9 for prime factors
Examples
- Input
- arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4], num = 12
- Output
- max_subarray = 6 ([4, -1, 2, 1]), prime_factor_sum = 2 + 3 = 5
- Why
- Kadane's algorithm finds the max contiguous subarray sum. Prime factors of 12 are 2 and 3, sum is 5.
Approach
Understand whether prime factor sum includes duplicate prime factors or distinct ones.
Check all subarrays for maximum sum O(n^2), and trial division up to n for prime factors.
Use Kadane's algorithm for max subarray sum in O(n) time. Use trial division up to sqrt(n) to find prime factors in O(sqrt(n)) time.
All negative array elements; number is prime or 1.
Solution
O(n) time, O(1) space
def maxSubArraySum(arr):
max_so_far = curr_max = arr[0]
for x in arr[1:]:
curr_max = max(x, curr_max + x)
max_so_far = max(max_so_far, curr_max)
return max_so_far
Tips
- What they are testing: Test Kadane's with an array of all negative numbers. Test prime factor sum with prime numbers and composite numbers.
- Common mistake: Initializing max_sum to 0 in Kadane's algorithm, which fails if all numbers are negative.
Related Adobe questions
Collected from public candidate posts and coding forums. Updated Nov 2026.