Hackerrank - Array Manipulation

質問する
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.
入力値は、マトリクスのサイズ(m*n)とqueriesqueriesqueriesquery(演算子はa、b、k)を受け入れます.クエリの意味は、aが開始インデックスであり、bが終了インデックスであり、kが加算される値である.
行列内の各クエリは、配列のaインデックスからbインデックスにk値を加算する.その後、すべてのクエリーを実行し、配列内の要素の最大値を返します.
例
入力値

5 3
1 2 100
2 5 100
3 4 100

出力値

200

説明:

After the first update the list is 100 100 0 0 0 .

After the second update list is 100 200 100 100 100 .

After the third update list is 100 200 200 200 100 .

The maximum value is 200200200
に答える
1.Brute Forceプール(タイムアウト)

def arrayManipulation(n, queries):
    # Write your code here
    # k값을 더할 배열 생성
    sum_list = [0] * (n + 1)

    # 배열안에있는 쿼리를 돌면서 k값을 더한다.
    for i in queries:
        for j in range(i[0], i[1] + 1):
            sum_list[j] += i[2]
            
    # 최대값 반환
    return max(sum_list)

配列中のすべてのクエリに対して,k値を区間で加算し,最大値の解を求める.

時間複雑度はO(m≁n)=>O(n 2)O(m*n)=>O(n^2)O(m≁n)=>O(n 2)である.

2.Prefix Sum(区間和)を用いて解く

def arrayManipulation(n, queries):
    # Write your code here
    # 부분합 리스트
    k_list = [0] * (n + 1)

    # 리턴할 가장 높은 값
    max_val = 0

    # 부분합 리스트 업데이트
    for s, e, k in queries:
        k_list[s] += k
        if e + 1 <= n:
            k_list[e +1] -= k
    
    # max_val과 비교하기 위한 변수 설정
    val = k_list[0]

    # 부분합의 누적합을 구하면서 최대 값을 구한다.
    for i in range(1, n+1):
        val += k_list[i]
        if val > max_val:
            max_val = val
            
    return max_val

区間と全区間の和を求めるのではなく,開始インデックスと終了インデックスにその区間の値を格納し,その格納値を積算値リストとして最大値の解を求める.

接頭辞と概念

Prefix Sumにより,時間的複雑度O(n 2)=>O(n^2)=>O(n)O(n 2)=>O(n)となり,性能はさらに向上した.

この問題は簡単そうに見えるが、解答するとタイムアウトし、時間の複雑さを減らすことで解決するのは難しい.また,区間プロトコルの概念を理解することも容易ではない.