第2题

int solve(int n, int a[])
{
    int ret = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            int sum = 0;
            for (int k = j; k <= i; ++k)
            {
                sum += a[k];
            }
            ret += sum;
        }
    }
    return ret;
}

如果打算用更好的算法实现 solve 函数，那么最好的算法可以达到的时间复杂度为（ ）。

{{ select(1) }}

• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(n^2 \cdot \log n)$
• $\Theta(\log n)$