。重疊子數組的最大和
689。 3 個不重疊子數組的最大和
難度:難
主題:數組,動態規劃
給定一個整數數組 nums 和一個整數 k,找到三個長度為 k 且總和最大的不重疊子數組並傳回它們。
傳回結果作為表示每個間隔起始位置的索引清單(0-索引)。如果有多個答案,則傳回字典順序最小的一個。
範例1:
- 輸入: nums = [1,2,1,2,6,7,5,1], k = 2
- 輸出: [0,3,5]
-
解釋: 子數組 [1, 2], [2, 6], [7, 5] 對應於起始索引 [0, 3, 5]。
- 我們也可以採用 [2, 1],但是 [1, 3, 5] 的答案會依照字典順序會更大。
範例2:
- 輸入: nums = [1,2,1,2,1,2,1,2,1], k = 2
- 輸出: [0,2,4]
約束:
- 1 4
- 1 16
- 1
解:
我們將使用動態規劃法。這個想法是將問題分解為更小的子問題,利用子數組的重疊來有效計算長度為 k 的三個非重疊子數組的最大和。
方法:
預先計算長度為 k 的子數組的總和:
首先,我們計算輸入數組 nums 中所有長度為 k 的子數組的總和。透過使用滑動視窗技術,可以在線性時間內有效地完成此操作。動態規劃(DP):
我們建立兩個輔助數組(左數組和右數組)來儲存截至目前位置找到的最佳子數組的索引。 left[i] 將儲存在索引 i 之前結束的最佳子數組的索引,而 right[i] 將儲存在索引 i 之後開始的最佳子數組的索引。迭代併計算最大值和:
對於從索引 j 開始的每個可能的中間子數組,我們透過考慮 j 之前的最佳左子數組和 j 之後的最佳右子數組來計算總和。字典順序:
如果有多個有效答案(總和相同),我們會傳回字典順序最小的一個。這是透過迭代順序來確保的。
讓我們用 PHP 實作這個解:689。 3 個不重疊子數組的最大和
<?php /** * @param Integer[] $nums * @param Integer $k * @return Integer[] */ function maxSumOfThreeSubarrays($nums, $k) { ... ... ... /** * go to ./solution.php */ } // Test cases print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5] print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4] ?>
解釋:
-
子數組與計算:
- 我們計算長度為 k 的所有可能子陣列的總和。這是透過先計算前 k 個元素的總和來完成的。然後,對於每個後續位置,我們減去留下的元素並添加數組中的下一個元素,使其成為有效的滑動視窗方法。
-
左右數組:
- left[i] 保存在索引 i 之前結束且具有最大總和的子數組的索引。
- right[i] 保存從索引 i 之後開始的具有最大總和的子數組的索引。
-
最終計算:
- 對於每個中間子數組 j,我們檢查最佳左子數組和最佳右子數組的組合,如果總和大於當前最大值,則更新結果。
-
字典順序上最小的答案:
- 當我們從左到右迭代時,我們透過自然地選擇產生最大總和的第一個子數組來確保字典順序最小的解決方案。
例子:
輸入:
$nums = [1, 2, 1, 2, 6, 7, 5, 1]; $k = 2;
輸出將是:
[0, 3, 5]
這種方法確保了時間複雜度保持高效,時間複雜度約為 O(n),其中 n 是輸入數組 nums 的長度。
聯絡連結
如果您發現本系列有幫助,請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子? 。您的支持對我來說意義重大!
如果您想要更多類似的有用內容,請隨時關注我:
- 領英
- GitHub
以上是。重疊子數組的最大和的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

PHP和Python各有優勢,選擇依據項目需求。 1.PHP適合web開發,尤其快速開發和維護網站。 2.Python適用於數據科學、機器學習和人工智能,語法簡潔,適合初學者。

在PHP中,應使用password_hash和password_verify函數實現安全的密碼哈希處理,不應使用MD5或SHA1。1)password_hash生成包含鹽值的哈希,增強安全性。 2)password_verify驗證密碼,通過比較哈希值確保安全。 3)MD5和SHA1易受攻擊且缺乏鹽值,不適合現代密碼安全。

PHP在電子商務、內容管理系統和API開發中廣泛應用。 1)電子商務:用於購物車功能和支付處理。 2)內容管理系統:用於動態內容生成和用戶管理。 3)API開發:用於RESTfulAPI開發和API安全性。通過性能優化和最佳實踐,PHP應用的效率和可維護性得以提升。

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

HTTP請求方法包括GET、POST、PUT和DELETE,分別用於獲取、提交、更新和刪除資源。 1.GET方法用於獲取資源,適用於讀取操作。 2.POST方法用於提交數據,常用於創建新資源。 3.PUT方法用於更新資源,適用於完整更新。 4.DELETE方法用於刪除資源,適用於刪除操作。

在PHPOOP中,self::引用當前類,parent::引用父類,static::用於晚靜態綁定。 1.self::用於靜態方法和常量調用,但不支持晚靜態綁定。 2.parent::用於子類調用父類方法,無法訪問私有方法。 3.static::支持晚靜態綁定,適用於繼承和多態,但可能影響代碼可讀性。

PHP通過$\_FILES變量處理文件上傳,確保安全性的方法包括:1.檢查上傳錯誤,2.驗證文件類型和大小,3.防止文件覆蓋,4.移動文件到永久存儲位置。

PHP類型提示提升代碼質量和可讀性。 1)標量類型提示:自PHP7.0起,允許在函數參數中指定基本數據類型,如int、float等。 2)返回類型提示:確保函數返回值類型的一致性。 3)聯合類型提示:自PHP8.0起,允許在函數參數或返回值中指定多個類型。 4)可空類型提示:允許包含null值,處理可能返回空值的函數。
