京都大学 情報学研究科 知能情報学専攻 2022年2月実施 基礎科目 F2-1

标签：

• Kyoto-University
• Algorithm-Complexity
• Maximum-Subarray-Sum

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Q.1

The following function func returns the largest value of $A[j]-A[i]$ with $i\le j$, given an integer array $A$ of size $n$.

int func(int A[], int n) {
    int d = 0;

    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++)
            if (A[j] - A[i] > d)
                d = A[j] - A[i];

    return d;
}

(1) Describe the time complexity of the algorithm with reasons.

(2) If an algorithm with better time complexity exists, give its code and time complexity.

Q.2

A maximum value contiguous subsequence (MVCS) is a contiguous subsequence of an integer sequence whose element sum is maximum among all contiguous subsequences. For example, an MVCS of [-5, 3, 7, -4] is [3, 7], with sum $10$, and an MVCS of [-5, 3, 7, -4, 5, 3, -20] is [3, 7, -4, 5, 3], with sum $14$.

Give an efficient algorithm that computes the sum of an MVCS of a length-$n$ sequence $A$, and state its time complexity.

题目描述

1. 题给双重循环函数 func，其返回整数数组 $A$ 中 $i\le j$ 时 $A[j]-A[i]$ 的最大值。
   1. 说明该算法的时间复杂度；
   2. 若有更快算法，写出代码及其时间复杂度。
2. 最大值连续子序列（MVCS）是元素和在所有连续子序列中最大的连续子序列。 给出计算长度为 $n$ 的整数序列 $A$ 的 MVCS 元素和的高效算法，并回答时间复杂度。

Kai

Q.1

(1)

For each $i$, the inner loop executes $n-i$ times. Hence the total number of iterations is

$$\sum_{i=0}^{n-1}(n-i)=\frac{n(n+1)}2.$$

Each iteration takes constant time, so the running time is

$$\boxed{\Theta(n^2)}.$$

(2)

Maintain the minimum value seen at an index not exceeding the current $j$.

int func_linear(int A[], int n) {
    int d = 0;
    int min_value = A[0];

    for (int j = 0; j < n; j++) {
        if (A[j] - min_value > d)
            d = A[j] - min_value;
        if (A[j] < min_value)
            min_value = A[j];
    }
    return d;
}

Immediately before the first comparison at iteration $j$, min_value is the minimum of the preceding values (with A[0] used when $j=0$). If A[j] is a new minimum, choosing $i=j$ gives $A[j]-A[j]=0$, which is already covered by d = 0. After the second comparison, min_value equals $\min\{A[0],\ldots,A[j]\}$. Thus the algorithm considers the best valid $i$ for every $j$. It uses

$$\boxed{\Theta(n)\text{ time and }\Theta(1)\text{ extra space}.}$$

Q.2

For a nonempty MVCS, Kadane's algorithm is

ending = A[0]
best   = A[0]

for i = 1 to n - 1:
    ending = max(A[i], ending + A[i])
    best   = max(best, ending)

return best

After processing $A[i]$, ending is the largest sum of a contiguous subsequence ending exactly at $i$, while best is the largest sum seen at any ending position. Thus the returned value is the MVCS sum.

The loop examines each element once, so the complexity is

$$\boxed{\Theta(n)\text{ time and }\Theta(1)\text{ extra space}.}$$