配列問題のTLEを解決したい

前提・実現したいこと

競技プログラミングの以下の問題を解決したいです。
問題のURL：https://www.codewars.com/kata/5ce399e0047a45001c853c2b/train/php

ls = [0, 1, 3, 6, 10] // 入力

ls = [0, 1, 3, 6, 10]
ls = [1, 3, 6, 10]
ls = [3, 6, 10]
ls = [6, 10]
ls = [10]
ls = []

// 対応する和をリストにまとめて表示
[20, 20, 19, 16, 10, 0] // 出力

発生している問題・エラーメッセージ

　ある程度のサイズの配列なら大丈夫なのですが、大きすぎる配列だと

Execution Timed Out (12000 ms)

とエラーが出るので、処理の冗長を無くさなくてはいけません。
（このエラーが発生している時の入力配列は、競プロのシステム上見ることができないです。。。）

該当のソースコード

php
1function partsSums($ls) {
2  $result_array = [];
3  $length = count($ls);
4  $tmp = 0;
5  for($i = 0; $i < $length; $i++) {
6    $tmp += array_pop($ls);
7    array_unshift($result_array, $tmp);
8  }
9  $result_array[] = 0;
10  return $result_array;
11}

試したこと

繰り返し処理がおかしいと思い

  while(!empty($ls)) {
    $result_array[] = array_sum($ls);
    array_shift($ls);
  }

と書いてみたり

  for($i = $length - 1; $i >= 0; $i--) {
    $tmp += $ls[$i];
    array_unshift($result_array, $tmp);
  }

と書いてみましたが、結果はやはりタイムアウトエラーでした

原因と実装方法について、アドバイスを頂いてもよろしいでしょうか。

anozon

2020/08/04 02:00

問題のリンクはありますか？

KK0618

2020/08/04 02:02

こちらです！ https://www.codewars.com/kata/5ce399e0047a45001c853c2b/train/php

行動規範の内容に同意します

回答2件

問題のURLがないので最悪ケースのテストができないのですが
array_shift, array_unshift は言語によっては O(1)でなく O(n) の場合があります。

ループ内でpush、最後に array_reverse する実装に変更してもLTEになりますか？

投稿2020/08/04 02:03

anozon

総合スコア662

KK0618

2020/08/04 02:21

anozonさまありがとうございます！アドバイス通りに実装しましたら、TLEにならず、実装することができました！タッチの差で別のアンサーを頂きましたので、高評価とさせてください。。。 arra_shiftやarray_unshiftがO(n)になってしまうとは予想もしていませんでした。勉強になります！

行動規範の内容に同意します