Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

$A$ is an array of length $n$

$B$ is an $n\times n$ matrix \

I want to return an array C of size n such that:

$$C_{i} = \sum_{j=1}^{n} \max(0, a_i - b_{ij}) $$

In pseudocode it could be like below

for i = 1 to n:
   C[i] = 0
   for j = 1 to n:
      C[i] += max(0, a[i] - b[i,j])

this runs on O(n^2) but it is possible to lower that.

That's not possible. You have to read in the entire $B$ matrix to determine the correct answer, which fundamentally requires $O(n^2)$ time.

StackExchange Computer Science Q#154386, answer score: 30