โ† Adobe questions

Largest Sum Contiguous Subarray and Sum of Prime Factors

Filed under Adobe

Free read 2 of 3

Understand 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

  1. Understand whether prime factor sum includes duplicate prime factors or distinct ones.

Solution

O(n) time, O(1) space

Python
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.