找到子陣列模的和M時

的最大值的問題是 - 你給出大小爲N的一個陣列和另一個整數M.你的目標是找到子陣列模的總和的最大值M.找到子陣列模的和M時

If array is {3 3 9 9 5} and M is {7}

可能的子陣列是

{3},{3},{9}.{9}.{5} 
{3,3},{3,9},{9,9},{9,5} 
{3,3,9},{3,9,9},{9,9,5} 
{3,3,9,9},{3,9,9,5},{3,3,9,9,5}

外面最大可能的總和取模7將6.子陣{3,3}具有最大總和。

我遇到了解決方案，但無法理解其中的邏輯

static void solve(long M, long[] array){ 
    TreeSet<Long> sumSet = new TreeSet<Long>(); 
    long best = 0; 
    long sum = 0; 

    for(int i = 0; i < array.length; i++){ 

     sum = (sum + array[i]) % M; 
     Long up = sumSet.higher(sum); 
     if(up == null){ 
      best = Math.max(best,sum); 
     } else { 
      best = Math.max(best, M - up + sum); 
     } 
     sumSet.add(sum); 
    } 

    System.out.println(best); 
}

什麼是線意味着

best = Math.max(best, M - up + sum);

來源

2016-06-08 Ad-vic

在模運算，加上除數的結果不會使區別。例如，-1 (mod N)與N-1相同。在您的算法中，M - up + sum從sum減去up，並且由於它始終爲負數，因此添加M以使結果爲正。

算法在做什麼？

迭代陣列上方，並使用可變sum
保持運行sum存儲到TreeSet保持的運行總和。這個想法是能夠在O(log N)中提取總和。 sum - (any number from sumSet)是一個子數組的總和。如果結果爲負，則合計M給出子陣列的正數總和。
從sumSet中提取大於sum的最小整數。爲什麼？可能的最大總和是最不利的。可能的最大模數爲M - 1。當sum - up等於-1時獲得。
如果沒有此類以前的總和，請將當前的sum與best進行比較。
否則，比較sum - up + M與best。

複雜：在O（n）的歌廳的O(n log n)

來源

2016-06-08 18:40:30

很好的解釋..was思維，但堂妹的TreeSet中的O（nlogn）。但它比產生所有子集和檢查哪個會導致O（n2）更好， –

找到子陣列模的和M時

回答

相關問題