假设线性表中的数据元素类型为int，请编写函数求线性表的最大元素。分别在顺序表和单链表上实现，并分析时间复杂性C++

在C++中，我们可以为顺序表和单链表编写两个求最大元素的函数。这里以`std::vector<int>`表示顺序表（数组），`ListNode<int>*`表示单链表的头节点。

**顺序表（数组）实现：**

#include <vector>
using namespace std;

// 返回数组中最大元素
int findMaxInArray(vector<int>& nums) {
    if (nums.empty()) return INT_MIN; // 防止空数组
    int max_val = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        if (nums[i] > max_val) {
            max_val = nums[i];
        }
    }
    return max_val;
}

**单链表实现：**

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 返回链表中最大元素
int findMaxInLinkedList(ListNode* head) {
    if (head == nullptr) return INT_MIN; // 链表为空
    int max_val = head->val;
    while (head != nullptr) {
        if (head->val > max_val) {
            max_val = head->val;
        }
        head = head->next;
    }
    return max_val;
}

**时间复杂性分析：**
- 对于顺序表，我们遍历整个数组一次，时间复杂度为O(n)，其中n是数组长度。
- 对于单链表，因为我们需要逐个节点查找，所以时间复杂度也为O(n)，其中n是链表的长度。