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