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

算法设计与分析通常关注如何有效地解决特定问题，这里我们讨论的是在一个只包含整数`int`的线性表（无论是顺序表还是单链表）中查找最大元素。

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

#include <vector>
int findMax(int* arr, int n) {
    if (n == 0) return INT_MIN; // 防止空数组
    int max = arr[0]; // 假设第一个元素是最大的
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

**时间复杂性**: 这种方法的时间复杂度是O(n)，因为需要遍历整个数组一次。

**单链表实现**:

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

int findMax(ListNode* head) {
    if (!head || !head->next) return head->val; // 如果链表为空或只有一个节点
    int max = head->val;
    ListNode* current = head->next;
    while (current) {
        if (current->val > max) max = current->val;
        current = current->next;
    }
    return max;
}

**时间复杂性**: 单链表的情况同样需要遍历每个节点，所以时间复杂度也是O(n)，其中n是链表的长度。

**相关问题--:**
1. 顺序表和单链表在查找最大元素时，空间复杂度有何区别？
2. 如果线性表中有重复的最大元素，这两种方法会怎么处理？
3. 除了顺序遍历，还有哪些更高效的方法可以在不修改原有结构的情况下找到最大值？