<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 1014. 最佳觀光組合 ## 題目地址(1014. 最佳觀光組合) <https://leetcode-cn.com/problems/best-sightseeing-pair/> ## 題目描述 ``` <pre class="calibre18">``` 給定正整數數組 A,A[i] 表示第 i 個觀光景點的評分,并且兩個景點 i 和 j 之間的距離為 j - i。 一對景點(i < j)組成的觀光組合的得分為(A[i] + A[j] + i - j):景點的評分之和減去它們兩者之間的距離。 返回一對觀光景點能取得的最高分。 示例: 輸入:[8,1,5,2,6] 輸出:11 解釋:i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11 提示: 2 <= A.length <= 50000 1 <= A[i] <= 1000 ``` ``` ## 前置知識 - 動態規劃 ## 公司 - 阿里 - 字節 ## 思路 最簡單的思路就是兩兩組合,找出最大的,妥妥超時,我們來看下代碼: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">1</span>): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i + <span class="hljs-params">1</span>, n): res = max(res, A[i] + A[j] + i - j) <span class="hljs-keyword">return</span> res ``` ``` 我們思考如何優化。 其實我們可以遍歷一遍數組,對于數組的每一項`A[j] - j` 我們都去前面找`最大`的 A\[i\] + i (這樣才能保證結果最大)。 我們考慮使用動態規劃來解決, 我們使用 dp\[i\] 來表示 數組 A 前 i 項的`A[i] + i`的最大值。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) dp = [float(<span class="hljs-string">'-inf'</span>)] * (n + <span class="hljs-params">1</span>) res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): dp[i + <span class="hljs-params">1</span>] = max(dp[i], A[i] + i) res = max(res, dp[i] + A[i] - i) <span class="hljs-keyword">return</span> res ``` ``` 如上其實我們發現,dp\[i + 1\] 只和 dp\[i\] 有關,這是一個空間優化的信號。我們其實可以使用一個變量來記錄,而不必要使用一個數組,代碼見下方。 ## 關鍵點解析 - 空間換時間 - dp 空間優化 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) pre = A[<span class="hljs-params">0</span>] + <span class="hljs-params">0</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): res = max(res, pre + A[i] - i) pre = max(pre, A[i] + i) <span class="hljs-keyword">return</span> res ``` ``` ## 小技巧 Python 的代碼如果不使用 max,而是使用 if else 效率目測會更高,大家可以試一下。 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxScoreSightseeingPair</span><span class="hljs-params">(self, A: List[int])</span> -> int:</span> n = len(A) pre = A[<span class="hljs-params">0</span>] + <span class="hljs-params">0</span> res = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): <span class="hljs-title"># res = max(res, pre + A[i] - i)</span> <span class="hljs-title"># pre = max(pre, A[i] + i)</span> res = res <span class="hljs-keyword">if</span> res > pre + A[i] - i <span class="hljs-keyword">else</span> pre + A[i] - i pre = pre <span class="hljs-keyword">if</span> pre > A[i] + i <span class="hljs-keyword">else</span> A[i] + i <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度:O(N)O(N)O(N) - 空間復雜度:O(N)O(N)O(N) 大家對此有何看法,歡迎給我留言,我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫:<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看