 # The maximum sum value of ranges — Ultimate version – Codewars

Have you solved the simple version and the challenge version? Now, the ultimate version is coming :]. The difference between this version and the challenge version is:

``the element of range from [start,end] into [start,end,num] ``

That is, before we calculate the sum value, we need to replace the element with `num` at the start index.

Given an array `arr` that contains some integers(positive, negative or 0), and a `range` list such as `[[start1,end1,num1],[start2,end2,num2],...]`, start and end are the index of `arr` and start always less than end. Your task is replace the value of arr[start] with `num`, and then calculte the sum value of each range (start index and end index are both inclusive), and return the maximum sum value.

For example:

``````Given arr = [1,-2,3,4,-5,-4,3,2,1],
range = [[1,3,5],[0,4,2],[6,8,1]]
should return 12

calculte process:
step 1:
replace arr with 5
then arr = [1,5,3,4,-5,-4,3,2,1]
range[1,3] = arr+arr+arr = 5 + 3 + 4 = 12

step 2:
replace arr with 2
then arr = [2,5,3,4,-5,-4,3,2,1]
range[0,4] = arr+arr+arr+arr+arr
= 2 + 5 + 3 + 4 + -5 = 9
step 3:
replace arr with 1
then arr = [2,5,3,4,-5,-4,1,2,1]
range[6,8] = arr+arr+arr = 1 + 2 + 1 = 4

So the maximum sum value is 12``````

### Note:

• `arr` always has at least 5 elements;
• `range` always has at least 1 elements;
• The replacement operation is carried out step by step, according to the order of range. The replacement operations will affect the results of the calculations, please be careful 😉
• All inputs are valid;
• This is a ultimate version, Please optimize your algorithm to avoid time out 😉
• If you feel difficult, please try the simple version or try the challenge version.

• Basic test: 3 testcases
• Random test1: 100 testcases
• each arr : 5-100 elements
• each range : 1-6 elements
• Random test2: 100 testcases
• each arr : 100000 elements
• each range : 10000 elements

### Some Examples

``````maxSum([1,-2,3,4,-5,-4,3,2,1],[[1,3,5],[0,4,2],[6,8,1]]) === 12
maxSum([1,-2,3,4,-5,-4,3,2,1],[[1,3,10]]) === 17
maxSum([1,-2,3,4,-5,-4,3,2,1],[[1,4,6],[2,5,4]]) === 8``````
Codewars

## Brute Force

``````procedure maxSum(arr, range) // range is multidimensional array
1. set sum to -Infinity
2. for i equals 0 to range.length
A. set r to range[i]
B. arr[r] = r
C. set temp to 0
D. for j equlas 0 to arr.slice(r, r + 1) // start, end
I. temp += arr[j]
E. if temp > sum then sum = temp
3. return sum

``````

The runtime complexity of this algorithm is quadraticO(ra), where r is the array of ranges and a is the array.

By implementing fenwick tree we can improve the runtime of this algorithm to run at O(Rlog A[start], A[end]:A), in which the upper bound is much closer to linear time – O(Rlog A[start], A[end]:A) = O(log n + n) = O(n).

## Using Binary Indexed Tree

``````procedure maxSum(arr, range)
1. set tree to arr
2. for i equals 0 to arr.length // the upper bound O(n)
A. set j to bit representation of i
B. if j < arr.length then tree[j] += tree[i];
3. set max to -Infinity
4. for each start, end, num in range // O(n)
A. set i to start, v to num - arr[start], n to arr.length, sum to 0
B. while i < n // O(log n)
I. tree[i] += v
II. assign to i itself + 1 binary representtional value
C. i = end
D. while i >= start && i <= end // O(log n)
I. sum += tree[i]
II. i equals i and i+1 binary representation
III. i--
E. if sum > max then max = sum
5. return max
``````