Array Maximum Value
Similar Problems:
Description Given an array a containing n positive integers, there is another array b of length n, indicating that the value of the i positive integer is b[i]. We can choose any non-intersecting interval [i, j], which needs to satisfy i < j and a[i] = a[j], then we can get all the numbers’ value in intervals [i, j] , that the value of b[i] + b[i+1] + … + b[j]. Output the maximum value of the array you can get.
2 <= n <= 1e5 1 <= a[i], b[i] <= 1e3
Example
Given a = [1,2,3,4,5,6], b = [1,1,1,1,1,1],return 0. Explanation: Because there are no equal numbers in the array a, no interval can be selected. The maximum value that can be obtained is 0
Given a = [4,2,2,1,2,1], b = [1,2,1,2,1,100],return 106. Explanation: Because all the intervals selected can't intersect, we should choose the interval: [1,2], [3,5] a[1] = a[2] = 2 a[3] = a[5] = 1 The values that can be obtained at this time are: b [1] + b [2] + b [3] + b [4] + b [5] = 106
Github: code.dennyzhang.com
Credits To: lintcode.com
Leave me comments, if you have better ways to solve.
- Solution:
General Thinkings:
Key Observations:
Walk Through Testdata
// https://code.dennyzhang.com/array-maximum-value
