Sum of Scores of Subarray
https://leetcode.com/discuss/interview-question/1706805/Amazon-OA-Question-Is-there-an-O(n)
Last updated
Was this helpful?
https://leetcode.com/discuss/interview-question/1706805/Amazon-OA-Question-Is-there-an-O(n)
Last updated
Was this helpful?
Given an array "points" of numbers, a score can be calculated for a subarray [i....j] by...
score = min(points[i...j])*sum(points[i...j[)
return the sum of all scores of all possible subarrays.
For example, points = [2,1,3] in the form index pair = score 0,0 = 4 0,1 = 3 0,2 = 6 1,1 = 1 1,2 = 4 2,2 = 9
total = 27
For an array of size n, calculate the sum of power of every subarray. Power of subarray [i, j] is min(i, j) * sum(i, j). Sum of power of every subarray in [2,3,2,1] is 69 (36 + 25 + 7 + 1): [2]: 2 * 2 = 4, [2, 3]: 2 * 5 = 10, [2,3,2]: 2 * 7 = 14, [2, 3, 2, 1]: 1 * 8 = 8 [3]: 3 * 3 = 9, [3,2]: 2 * 5 = 10, [3,2,1]:1 * 6 = 6 [2]: 2 * 2 = 4, [2, 1]: 1 * 3 = 3 [1]: 1 * 1 = 1