（2）对3种策略每一种分别找出1个问题（要求不是课本中的例题）用相应的算法设计策略解决。写出问题定义，解决问题算法的自然语言描述和C++语言描述，分析解决问题算法的时间复杂性等。

1. 问题定义：给定一个长度为n的数组，求其最大子序列和。

解决问题算法：

- 分治法：将问题分成两个子问题，分别求解左半部分的最大子序列和、右半部分的最大子序列和和跨越中点的最大子序列和，三者取最大值作为答案。

自然语言描述：将数组分为左右两部分，递归求解左半部分的最大子序列和、右半部分的最大子序列和和跨越中点的最大子序列和，三者取最大值作为答案。

C++语言描述：

int maxSubArray(int nums[], int left, int right) {
    if (left == right) return nums[left];
    int mid = left + (right - left) / 2;
    int leftMax = maxSubArray(nums, left, mid);
    int rightMax = maxSubArray(nums, mid + 1, right);
    int crossMax = nums[mid] + nums[mid + 1], leftSum = nums[mid], rightSum = nums[mid + 1];
    for (int i = mid - 1; i >= left; i--) {
        leftSum += nums[i];
        crossMax = max(crossMax, leftSum + nums[i]);
    }
    for (int i = mid + 2; i <= right; i++) {
        rightSum += nums[i];
        crossMax = max(crossMax, rightSum + nums[i]);
    }
    return max(leftMax, max(rightMax, crossMax));
}

时间复杂性：$O(n\log n)$

2. 问题定义：有n个任务需要完成，每个任务有一个截止时间和一个收益。每个任务需要占用一个单位时间，求在给定时间内完成任务的最大收益。

解决问题算法：

- 动态规划法：设f(t)为在时间t内完成任务的最大收益，则有$f(t) = \max\{f(t-1),\max\limits_{i=1}^{n}\{f(t-t_i)+v_i\}\}$。

自然语言描述：对于每个时间t，计算在该时刻完成任务的最大收益，最终返回完成任务的最大收益。

C++语言描述：

int maxProfit(int n, int t[], int v[]) {
    int f[n+1], ans = 0;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++) {
        for (int j = t[i]; j >= 1; j--) {
            f[j] = max(f[j], f[j-1] + v[i]);
            ans = max(ans, f[j]);
        }
    }
    return ans;
}

时间复杂性：$O(nt)$

3. 问题定义：给定一个无向图G=(V,E)，其中V为点集合，E为边集合，每条边有一个权值，求一棵生成树，使得其所有边的权值之和最小。

解决问题算法：

- 贪心算法：使用Kruskal算法，将边按照权值从小到大排序，然后依次加入到生成树中，如果加入该边后会形成环，则舍弃该边。

自然语言描述：将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入该边后会形成环，则舍弃该边，直到生成树包含所有节点。

C++语言描述：

struct edge {
    int from, to, w;
    bool operator<(const edge& e) const {
        return w < e.w;
    }
};

int find(int x, vector<int>& p) {
    return p[x] == x ? x : p[x] = find(p[x], p);
}

int minSpanningTree(int n, vector<edge>& edges) {
    sort(edges.begin(), edges.end());
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;
    int ans = 0;
    for (int i = 0; i < edges.size(); i++) {
        int x = find(edges[i].from, p);
        int y = find(edges[i].to, p);
        if (x != y) {
            p[x] = y;
            ans += edges[i].w;
        }
    }
    return ans;
}

时间复杂性：$O(m\log m)$，其中m为边数。