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
numat the start index.
Given an array
arrthat contains some integers(positive, negative or 0), and a
rangelist such as
[[start1,end1,num1],[start2,end2,num2],...], start and end are the index of
arrand 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.
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
arralways has at least 5 elements;
rangealways 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
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
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 quadratic – O(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