7-5 sdut-最长上升子序列的和

最长上升子序列（Longest Increasing Subsequence，简称 LIS）是指在一个无序的数列中，找到一个尽可能长的单调递增的子序列，例如对于序列 [1, 7, 3, 5, 9, 4, 8]，其中的最长上升子序列是 [1, 3, 5, 9] 或者 [1, 3, 4, 8]，长度为 4。

现在给定一个数列，你需要计算出它的最长上升子序列的和。例如对于序列 [1, 7, 3, 5, 9, 4, 8]，其最长上升子序列为 [1, 3, 5, 9] 或者 [1, 3, 4, 8]，它们的和分别为 18 和 16，所以结果为 18。

解决这个问题可以使用动态规划算法。设 dp[i] 表示以第 i 个数结尾的最长上升子序列的和，则有：

dp[i] = max(dp[j] + nums[i])，其中 0 ≤ j < i 且 nums[j] < nums[i]

最终的结果为 dp 数组中的最大值。时间复杂度为 O(n^2)。

以下是代码实现：

相关问题

7-6 上升子序列SDUT

上升子序列是指在一个序列中，如果一些数字呈上升趋势排列，那么这些数字就可以组成一个上升子序列。比如序列 {1, 3, 5, 2, 4, 6} 中，{1, 3, 5} 和 {2, 4, 6} 就是两个上升子序列。

SDUT（Shandong University of Technology，山东理工大学）的上升子序列问题是这样的：给定一个长度为 n 的序列，找出其中的一个最长的上升子序列。例如，对于序列 {1, 4, 3, 5, 6, 2}，其最长的上升子序列为 {1, 4, 5, 6}，长度为 4。

求解这个问题可以使用动态规划算法。我们可以定义一个数组 dp，其中 dp[i] 表示以第 i 个数字为结尾的最长上升子序列的长度。初始时，dp[i] 的值都为 1，因为每个数字本身就可以组成一个长度为 1 的上升子序列。然后，我们从第 2 个数字开始依次计算 dp[i] 的值，计算方法如下：

- 对于第 i 个数字，我们枚举它前面的所有数字 j，如果 j 小于 i，那么 dp[i] 的值可以更新为 dp[j]+1（因为以 j 为结尾的最长上升子序列再加上数字 i 就可以得到以 i 为结尾的最长上升子序列）。
- 在枚举 j 的过程中，我们还需要维护一个变量 max_len，它表示所有 dp[j]+1 的最大值。这是因为以 i 为结尾的最长上升子序列并不一定是以 j 为结尾的最长上升子序列再加上一个数字 i 得到的，有可能是以 j 为结尾的最长上升子序列和以 i 为结尾的最长上升子序列中的某个更长的子序列拼接得到的。
- 最终，我们遍历整个 dp 数组，找出其中的最大值即可。

下面是 Python 代码实现：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    max_len = 1
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
        max_len = max(max_len, dp[i])
    return max_len

时间复杂度为 O(n^2)。

7-3 sdut-String-5 图书价格汇总（II）用Java写代码

以下是一个使用 Java 写的图书价格汇总程序，使用了 HashMap 和 DecimalFormat 类：

import java.util.HashMap;
import java.text.DecimalFormat;
import java.util.Scanner;

public class BookPriceSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        DecimalFormat df = new DecimalFormat("0.00");

        HashMap<String, Double> map = new HashMap<String, Double>();
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            String name = sc.next();
            double price = sc.nextDouble();
            if (map.containsKey(name)) {
                price += map.get(name);
            }
            map.put(name, price);
        }

        for (String name : map.keySet()) {
            System.out.println(name + " " + df.format(map.get(name)));
        }
    }
}

程序首先读入图书的数量 n，然后使用一个 HashMap 来存储每种图书的价格总和。

接着循环读入每本图书的名称和价格，如果该图书已经存在于 map 中，则将该图书的价格加上之前已经存储的价格总和，最后将新的价格总和存储到 map 中。

最后遍历 map，输出每种图书的名称和价格总和。在输出价格时，使用 DecimalFormat 类来保留两位小数。