使用Kadane算法的最大子陣列模數

我正在嘗試解決hackerrank問題 - 最大子數組模數 - 這裏描述的是https://www.hackerrank.com/challenges/maximum-subarray-sum/problem。我很好奇這個問題是否可以用Kadane算法解決。使用Kadane算法的最大子陣列模數

目標：給定一個n元素的整數數組和一個整數'm'，確定其任何子模數'm'的總和的最大值。

輸入格式：

1）第一行包含一個整數「Q」表示查詢執行的數目。每條查詢用兩行描述：

a）第一行包含兩個空格分隔的整數，描述了數組長度和模數。

b）第二行包含空格分隔的整數，描述數組的元素。

這是我想出的可能的C++代碼。它在一些測試用例中失敗（對不起，測試用例太大而無法在這裏發佈）。您可以評論/評論爲什麼這可能無效嗎？謝謝。

#include <bits/stdc++.h> 

int main() 
{ 
    uint64_t q = 0, n = 0, m = 0; 

    std::cin >> q; 
    std::cin >> n; 
    std::cin >> m; 

    while(q) { 
     std::vector<uint64_t> vec; 
     for (uint64_t i = 0; i < n; i++) { 
      uint64_t num; 
      std::cin >> num; 
      vec.push_back(num); 
     } 
     uint64_t subArrayMax = 0; 
     uint64_t maxMod = 0; 
     for (uint64_t i = 0; i < n; i++) { 
      // Kadane's algorithm. 
      subArrayMax = std::max(subArrayMax, subArrayMax+vec[i]); // try (a+b)%m=(a%m+b%m)%m trick? 
      maxMod = std::max(maxMod, subArrayMax % m); 
     } 
     std::cout << maxMod; 
     --q; 
    } 
}

來源

2017-07-11 cpuNram

子陣列需要是連續的？ –

嘗試找到一個算法失敗的小例子。比這個例子回來。 – MrSmith42

Kadane的算法在這裏不適用，因爲它涉及模算術的屬性。

首先，你必須明白，爲什麼Kadane的算法的工作：這是一個簡單的動態規劃，回答了以下問題：

如果我們知道指數最大和最終的i-1，則最大總和在最後我要麼在附加a[i]到子陣列得到答案的i-1，或不附加它

隨着模運算，第是行不通的。對於如：

Let A = {1,2,3,4}, M = 6

隨着Kadane的算法，當然，最大的總和添加所有元素，它可以使用上面引述的思想中找到：保持附加a[i]到以前發現的最大總和。

但是，如果我們發現最大總和％6，則答案爲（2 + 3）％6 = 5，但不（1 + 2 + 3）％6 = 0或（1 + 2 + 3 4）％6 = 4越大最大總和NOT IMPLIES更優化的總和最大總和％M。因此，你的目標是甚至沒有發現的最高金額。

此問題可以在O(N lg N)中使用Kadane算法的修改版本來解決。

對於一個特定的索引我，

讓DP(i) =最大子陣列總和％M端在我

讓PS(i)處於我

的前綴和％M端當然，你會開始思考如何找到(PS(i) - PS(j)+ M) % M是最大的j < i。（假設你知道如何預先計算PS和基本模運算）

這是最核心的部分：原來

DP（I）= MAX（PS（I），（PS（ ⅰ） - PS（J）+ M）％M

凡PS（J'）是最小數目較大比PS （i）有沒有j < i

爲什麼？因爲看公式，如果PS(j') < PS(i)，那麼它當然更好不是減去PS(i)的任何東西。

但是，如果PS(j') > PS(i)，那麼我們就可以改寫這樣的公式：(M - x)%M，那麼我們希望x = PS(j')-PS(i)儘可能小，這樣(M - x)%M是最大的。

與Kadane的算法相同，我們跟蹤在整個過程中找到的最大答案。

我們可以使用優先級隊列或者設置數據結構來查找所有i在線的j'，總計達到O(N lg N)。詳情你可以在下面看到接受的代碼：

#include<bits/stdc++.h> 
#define LL long long 
using namespace std; 

int T; 
set<LL> pre; 
LL n, M, a[100010], ans, sum; 

int main() { 
    cin >> T; 
    while(T--){ 
     ans = sum = 0; 
     pre.clear(); 
     cin >> n >> M; 
     for(int i=0; i<n;i++) cin >> a[i]; 
     for(int i=0; i<n; i++){ 
      (sum += a[i]) %= M; 
      ans = max(ans, sum); 
      ans = max(ans, (sum - *(pre.upper_bound(sum))+M)%M); 
      pre.insert(sum); 
     } 
     cout << ans << endl; 
    } 
    return 0; 
}

來源

2017-07-11 07:59:27 shole

感謝@shole瞭解詳情。現在理解問題的根源。 – cpuNram

使用Kadane算法的最大子陣列模數

回答

相關問題