LintCode: Array Maximum Value

Array Maximum Value

Similar Problems:

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


Given a = [1,2,3,4,5,6], b = [1,1,1,1,1,1],return 0.

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.

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


Credits To:

Leave me comments, if you have better ways to solve.

  • Solution: XXX

General Thinkings:

Key Observations:

Walk Through Testdata

// Blog link:


Share It, If You Like It.

Leave a Reply

Your email address will not be published.