タスクは並行して進められるので、前提関係を満たして着手可能になったタスクは、その時点で着手するのが最適です。

よって、各タスクについて「前提となっている、開始時刻がまだ決まっていないタスクの個数」を管理し、これが 0 になったタスクから順に開始時刻を決めていけばよいです。

擬似コード

prereq_count = [...]  // prereq_count[i] = タスク i の前提となっているタスクの個数
ans = [None, ...]  // 答えの配列
queue = []  // 開始時刻が確定したタスクのキュー

for i in 1..N:
  if タスク i に前提がない:
    queue.push(i)

while True:
  i = queue.pop()
  ans_i = 0
  for pre in タスク i の前提になるタスク:
    ans_i = max(ans_i, ans[pre] + a[pre])
  ans[i] = ans_i
  for nxt in タスク i が前提になるタスク:
    prereq_count[nxt] -= 1
    if prereq_count[nxt] == 0:
      queue.push(nxt)

ここから更に、タスクの開始時刻の計算を、前提となるタスクが処理されたタイミングに変更することで、実装がより単純になります。

計算量は \(O(N+M)\) です。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<vector<int>> g(n);
  vector<int> deg(n);
  for(int i=0; i<m; i++){
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    deg[v]++;
  }

  queue<int> q;
  for(int i=0; i<n; i++){
    if(deg[i] == 0){
      q.push(i);
    }
  }
  vector<long long> ans(n);
  while(q.size() > 0){
    int v = q.front(); q.pop();
    for(auto nxt: g[v]){
      ans[nxt] = max(ans[nxt], ans[v] + a[v]);
      deg[nxt]--;
      if(deg[nxt] == 0){
        q.push(nxt);
      }
    }
  }

  if(!all_of(deg.begin(), deg.end(), [](long long x){return x==0;})){
    cout << -1 << endl;
  }else{
    long long ans_max = 0;
    for(int i=0; i<n; i++){
      ans_max = max(ans_max, ans[i] + a[i]);
    }
    cout << ans_max << endl;
  }
}

実装例 (Python)

N, M = map(int, input().split())
A = list(map(int, input().split()))
G = [[] for _ in range(N)]
deg = [0]*N
for _ in range(M):
  U, V = map(int, input().split())
  U -= 1
  V -= 1
  G[U].append(V)
  deg[V] += 1

q = [i for i in range(N) if deg[i]==0]
ans = [0] * N
for v in q:
  for nxt in G[v]:
    ans[nxt] = max(ans[nxt], ans[v] + A[v])
    deg[nxt] -= 1
    if deg[nxt] == 0:
      q.append(nxt)

if not all(deg[i]==0 for i in range(N)):
  print(-1)
else:
  print(max(ans[i] + A[i] for i in range(N)))