【软件设计师备考 专题 】算法探索：排序、查找、数值计算和字符串处理（三）

#include <iostream>
#include <vector>
#include <algorithm>
// 动态规划求解最长递增子序列问题
int longestIncreasingSubsequence(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);  // dp[i]表示以nums[i]结尾的最长递增子序列的长度
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    
    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        maxLength = std::max(maxLength, dp[i]);
    }
    
    return maxLength;
}
int main() {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    
    int maxLength = longestIncreasingSubsequence(nums);
    
    std::cout << "最长递增子序列的长度为：" << maxLength << std::endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
// 分治算法求解最大子数组和问题
int maxSubarraySum(std::vector<int>& nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    
    int mid = (left + right) / 2;
    
    int leftSum = maxSubarraySum(nums, left, mid);
    int rightSum = maxSubarraySum(nums, mid + 1, right);
    int crossSum = 0;
    
    int leftMaxSum = INT_MIN;
    int rightMaxSum = INT_MIN;
    
    for (int i = mid; i >= left; i--) {
        crossSum += nums[i];
        leftMaxSum = std::max(leftMaxSum, crossSum);
    }
    
    crossSum = 0;
    
    for (int i = mid + 1; i <= right; i++) {
        crossSum += nums[i];
        rightMaxSum = std::max(rightMaxSum, crossSum);
    }
    
    return std::max(std::max(leftSum, rightSum), leftMaxSum + rightMaxSum);
}
int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    int maxSum = maxSubarraySum(nums, 0, nums.size() - 1);
    
    std::cout << "最大子数组和为：" << maxSum << std::endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
// 图的邻接矩阵表示
class Graph {
public:
    Graph(int n) : numVertices(n), adjacencyMatrix(n, std::vector<int>(n, 0)) {}
    
    void addEdge(int u, int v, int weight) {
        adjacencyMatrix[u][v] = weight;
        adjacencyMatrix[v][u] = weight;
    }
    
    std::vector<int> dijkstra(int source) {
        std::vector<int> distance(numVertices, INT_MAX);
        std::vector<bool> visited(numVertices, false);
        distance[source] = 0;
        
        for (int i = 0; i < numVertices - 1; i++) {
            int u = getMinDistanceVertex(distance, visited);
            visited[u] = true;
            
            for (int v = 0; v < numVertices; v++) {
                if (!visited[v] && adjacencyMatrix[u][v] != 0 && distance[u] != INT_MAX
                    && distance[u] + adjacencyMatrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + adjacencyMatrix[u][v];
                }
            }
        }
        
        return distance;
    }
    
private:
    int getMinDistanceVertex(std::vector<int>& distance, std::vector<bool>& visited) {
        int minDistance = INT_MAX;
        int minVertex = -1;
        
        for (int v = 0; v < numVertices; v++) {
            if (!visited[v] && distance[v] <= minDistance) {
                minDistance = distance[v];
                minVertex = v;
            }
        }
        
        return minVertex;
    }
    
    int numVertices;
    std::vector<std::vector<int>> adjacencyMatrix;
};
int main() {
    Graph graph(6);
    
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 2, 2);
    graph.addEdge(1, 2, 1);
    graph.addEdge(1, 3, 5);
    graph.addEdge(2, 3, 8);
    graph.addEdge(2, 4, 10);
    graph.addEdge(3, 4, 2);
    graph.addEdge(3, 5, 6);
    graph.addEdge(4, 5, 3);
    
    std::vector<int> distance = graph.dijkstra(0);
    
    std::cout << "从顶点0到其他顶点的最短路径：" << std::endl;
    for (int i = 0; i < distance.size(); i++) {
        std::cout << "顶点" << i << "的最短路径长度为：" << distance[i] << std::endl;
    }
    
    return 0;
}