I was asked this question and could only come up with brute-force approach
Example - [1 9 -2 9 4 2 4]
Ans - [9 -2 9] = 16
Example - [9 -18 9 2 9]
Ans - 9+2+9 = 20
Example - [5,1,4,1,10,1,7]
Ans - 1+4+1+10+1 = 17
-
Was your brute force approach O(n^3)? If so, it can be easily reduced to O(n^2) by maintaining a prefix-sum array. The prefix sum array takes O(n) to precompute, but this would help you to find sum between any two indices in O(1). An alternative to prefix-sum array is to just maintain a variable to keep track of sum as you add or remove indices.Cherubim– Cherubim2021-05-28 18:52:05 +00:00Commented May 28, 2021 at 18:52
-
@Cherubim I solved the brute force approach in O(n^2)Kirti Kedia– Kirti Kedia2021-05-29 06:16:47 +00:00Commented May 29, 2021 at 6:16
Add a comment
|
1 Answer
We can use Kadane's algorithm but instead of single values, we need to add subarray sums. We can keep a record of the best starting index per value. Python code:
def f(A):
# Prefix sums
ps = [0] * (len(A) + 1)
for i in range(len(A)):
ps[i] = A[i] + ps[i-1]
# Map of value to its
# best starting index.
h = {}
# Best overall sum
best_sum = 0
for i in range(len(A)):
# We extend the interval by keeping the same
# starting index; Otherwise, reset the starting
# index.
if (not A[i] in h) or (ps[i] - ps[h[A[i]] - 1] <= 0):
h[A[i]] = i
candidate = ps[i] - ps[h[A[i]] - 1] if i != h[A[i]] else 0
best_sum = max(best_sum, candidate)
return best_sum
As = [
[1, 9, -2, 9, 4, 2, 4], # 16
[9, -18, 9, 2, 9], # 20
[5, 1, 4, 1, 10, 1, 7], # 17
[1, 2, 3] # 0
]
for A in As:
print(A)
print(f(A))
print('')
