2
\$\begingroup\$

Here's an interview question I've seen on a few sites. People claim that an O(n) solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.

Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.

Example input: (2, -1, -2, 1, -4, 2, 8)

Example output: ((1, 4), (5, 6))

The output above is the indices of these two subarrays: ((-1, -2, 1, -4,), (2, 8))

I've been trying to reduce this problem to the Maximum subarray problem but with no success.

Improve this question
\$\endgroup\$
9
  • 1
    \$\begingroup\$ This is off-topic for codegolf.stackexchange.com . To obtain the maximum/minimum subarray problem from this, you can compute the maximum/minimum subarray on all prefixes and all suffixes, and iterate over a "separator" index such that the maximum subarray and the minimum subarray lie to different sides of it. (that is, if you created arrays lmax, lmin, rmax, rmin, for i from 0 to n-1 ans = max(ans, rmax[i]-lmin[i], lmax[i]-rmin[i])) \$\endgroup\$
    – the default.
    Apr 11, 2020 at 15:26
  • 1
    \$\begingroup\$ I think the array with the bigger sum should be the maximum subarray, and the one with the smaller sum should be the reverse of that maybe (minimum subarray?). I think (this is pure intuition, I don't have an idea whether it's correct) you can run Kadane's on the array, negate all the elements, and run Kadane's again to find the maximum difference. With a few tweaks you should also be able to find the indices. And I feel this problem is not suited for codegolf.stackexchange.com \$\endgroup\$
    – Windmill Cookies
    Apr 11, 2020 at 15:27
  • \$\begingroup\$ Got a recommendation for a more fitting StackExchange site to ask this? \$\endgroup\$
    – Ram Rachum
    Apr 11, 2020 at 15:29
  • 2
    \$\begingroup\$ Probably Stack Overflow or Computer Science. Code Review might work if used correctly, but they'll probably simply micro-deoptimize your code to half the performance and tell you you aren't naming your variables right. For extremely extreme cases, CS Theory or Math Overflow might also work. \$\endgroup\$
    – the default.
    Apr 11, 2020 at 15:32
  • 1
    \$\begingroup\$ @mypronounismonicareinstate Please don't give answers or provide help for off topic questions. We should not be encouraging people to ask their questions here. If you really need to share just wait until it gets migrated and provide help there. \$\endgroup\$
    – Wheat Wizard ♦
    Apr 11, 2020 at 16:52

0

Reset to default

Browse other questions tagged or ask your own question.