題意

給定一個包含$n$個正整數的數組$a$，另外有一個長度為$n$的價值數組$b$，表示第$i$個正整數的價值為$b[i]$。我們可以選擇任意個不相交區(qū)間$[i,j]$，需要滿足$i<j$ 且$a[i]=a[j]$，隨后我們可以獲得區(qū)間$[i,j]$所有數的價值，即$b[i]+b[i+1]+...+b[j]$。
現在請輸出可以獲得的數組最大價值。

分析

此題由我改編自Hulu面試題，并上傳于Lintcode
題目鏈接

主要考察動態(tài)規(guī)劃算法

定義數組 $dp[i]$ ：前i個數構成的子數組能夠獲得的最大價值
則 $dp[n]$ 即為我們需要輸出的答案。

結合題意，求解$dp[i]$時需要考慮兩種情況：

沒有任何區(qū)間包含$a[i]$。那么b[i]最終不計入最大價值中，有 $dp[i]=dp[i?1]$

存在一個區(qū)間$[k,i]$ , 滿足$k<i$ 且 $a[k]=a[i]$， 那么 $$dp[i]=max\{dp[k?1]+(a[k]+a[k+1]+..+a[i])\}$$

如果處理一個前綴和數組， 記為sum，那么第二種情況的dp方程可以轉化為：

$$\begin{gathered} dp[i]=max\{dp[k?1]+sum[i]?sum[k?1]\} \\ =sum[i]+max\{dp[k?1]?sum[k?1]\} \end{gathered}$$

故如果在$i$ 前面存在多個 $k$ 滿足 $a[i]=a[k]$， 我們只需要找到最大的 $dp[k?1]?sum[k?1]$ 來轉移$dp$方程。
這個可以使用一個新數組$Mx$來維護，即對于每一個出現的數$a[k]$，我們都維護一下： $$Mx[a[k]]=max\{dp[k?1]?sum[k?1]\}$$

那么遍歷到$a[i]$時，只需要根據 $Mx[a[i]]$的值來轉移即可。

時間復雜度: O(n)

Code

C++

const int A = 1e5 + 10; const int B = 1e3 + 10; class Solution { public:/*** @param a: The array a* @param b: The array b* @return: Return the maximum value*/int dp[A], sum[A], Mx[B];bool vis[B];int getAnswer(vector<int> &a, vector<int> &b) {// Write your code hereint n = a.size(); sum[0] = 0;for (int i = 1; i <= n; i++) {sum[i] = sum[i - 1] + b[i - 1];}memset(vis, 0, sizeof(vis));dp[0] = 0;for (int i = 1; i <= n; i++) {if (!vis[a[i - 1]]) {vis[a[i - 1]] = 1;dp[i] = dp[i - 1];Mx[a[i - 1]] = dp[i - 1] - sum[i - 1];} else {dp[i] = max(dp[i - 1], Mx[a[i - 1]] + sum[i]);Mx[a[i - 1]] = max(Mx[a[i - 1]], dp[i - 1] - sum[i - 1]);}}return dp[n];} };

Java

public class Solution {/*** @param a: The array a* @param b: The array b* @return: Return the maximum value*/public int getAnswer(int[] a, int[] b) {// Write your code hereint dp[] = new int[100010];int pre[] = new int[100010];int Mx[] = new int[1010];boolean flag[] = new boolean[1010];pre[0] = 0;for (int i = 1; i <= a.length; i++) {pre[i] = pre[i - 1] + b[i - 1];}dp[0] = 0;for (int i = 1; i <= a.length; i++) {if (!flag[a[i - 1]]) {flag[a[i - 1]] = true;dp[i] = dp[i - 1];Mx[a[i - 1]] = dp[i - 1] - pre[i - 1];} else {dp[i] = max(dp[i - 1], Mx[a[i - 1]] + pre[i]);Mx[a[i - 1]] = max(Mx[a[i - 1]], dp[i - 1] - pre[i - 1]);}}return dp[a.length];}int max(int a, int b) {if (a > b) return a;return b;} }

Python

class Solution:"""@param a: The array a@param b: The array b@return: Return the maximum value"""def getAnswer(self, a, b):# Write your code heres = [0 for i in range(0, len(a))]dp = [0 for i in range(0, len(a))]same = [[] for i in range(0, 1010)]same[a[0]].append(0)s[0] = b[0]for i in range(1, len(a)):s[i] = s[i - 1] + b[i]same[a[i]].append(i)maxx = 0for j in range(1, len(same[a[0]])):dp[same[a[0]][j]] = s[same[a[0]][j]]same[a[0]].pop(0)for i in range(1, len(a)):if dp[i - 1] > maxx:maxx = dp[i - 1]for j in range(1, len(same[a[i]])):if dp[same[a[i]][j]] < maxx + s[same[a[i]][j]] - s[i - 1]:dp[same[a[i]][j]] = maxx + s[same[a[i]][j]] - s[i - 1]same[a[i]].pop(0)if dp[len(a) - 1] > maxx:maxx = dp[len(a) - 1]return maxx

總結

以上是生活随笔為你收集整理的[Hulu] 数组最大价值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。