一本通1598【 例 2】最大连续和

这是一个经典的动态规划问题，也被称为最大子序和问题。给定一个整数序列，找到其中连续子序列的最大和。

假设我们已经求出了前 i-1 个数的最大连续和 dp[i-1]，那么对于第 i 个数，它只有两种选择：

1. 加入前面的连续子序列，使得连续子序列的和变大。

2. 自己单独成为一个新的连续子序列。

因此，我们可以得到状态转移方程：

dp[i] = max(dp[i-1] + nums[i], nums[i])

其中 nums[i] 表示第 i 个数。

最终的答案就是所有 dp[i] 中的最大值。

代码实现如下：

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    int res = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
        res = max(res, dp[i]);
    }
    return res;
}

相关问题

「一本通 1.3 例 5」weight

### 回答1：
在「一本通 1.3 例 5」中，问题是关于重量的。根据题目，一个名叫小明的男孩站在一个测量体重的体重秤上。小明告诉我们他的体重是62千克。但是，老师告诉他他的测量结果有误。我们需要找出小明实际的体重是多少。

为了解决这个问题，我们需要知道秤的正确体重。根据题目，秤的刻度被调整过，而且没有提供正确的测量结果。所以我们需要另一个已知的重物来进行测量。

解决问题的关键是：将一个已知重物放在体重秤上来校正秤的刻度。在例题中，我们可以将一个10千克的重物放在秤上，并且秤显示它的重量是8千克。这意味着体重秤给出的重量少了2千克。

然后，我们再次称量小明的体重，结果为62千克。由于秤显示的重量少了2千克，小明实际的体重应该是62 + 2 = 64千克。

综上所述，「一本通 1.3 例 5」中，小明的实际体重应该是64千克。

### 回答2：
《一本通 1.3 例 5》中的问题提到了物体的重量。在物理学中，重量被定义为物体受到地球引力的作用而产生的力大小。重量通常用牛顿（N）作单位。

根据牛顿第二定律，物体的质量乘以加速度等于物体所受到的力。因此，可以使用下式计算物体的重量：

重量 = 质量 × 加速度

质量是物体所含有的物质的量度，通常使用千克（kg）作单位。而加速度在地球上通常被近似地看作是9.8 m/s²。因此，可以使用上述公式计算物体在地球上的重量。

例如，如果一个物体的质量是10千克，那么它在地球上的重量可以通过将质量乘以加速度来计算：

重量 = 10千克 × 9.8 m/s² = 98牛顿

所以，当一个物体的质量为10千克时，它在地球上的重量是98牛顿。

需要注意的是，重量是一个矢量量，它既有大小也有方向。在地球上，重力始终指向地心，所以地球上物体的重量方向往往指向地心。

总之，《一本通 1.3 例 5》中的问题涉及了物体的重量，它的大小可以通过物体的质量乘以加速度来计算，单位是牛顿。

### 回答3：
「一本通 1.3 例 5」的题目是关于重量的问题。

根据题目，小明和小红在街道上拾到一只大小相同的鸟笼，但是小明觉得鸟笼很重，而小红却认为鸟笼很轻。于是他们决定使用各自拥有的小物体来比较鸟笼的重量。

小明拿出一张纸巾，将纸巾摆在天秤左边，然后把鸟笼放在纸巾的右边。他发现纸巾的右边离天秤的中心更远，所以推断鸟笼比纸巾重。

小红则取来一张时间表，并将其放在天秤的左边，再将鸟笼放在时间表的右边。她发现时间表的右边离天秤的中心更近，因此认为鸟笼比时间表轻。

这两种方法都是利用天秤平衡的原理来推测鸟笼的重量。根据题目描述，小明和小红以不同的方式进行比较，因此得出了不同的结论。

这个题目通过简单的物理实验，引导我们思考物体的重量是如何影响天秤平衡的。它提醒我们，在进行物质比较时，需要仔细观察和分析实验结果，以得出准确的结论。同时，它也让我们明白了物体的重量是相对的，而不是绝对的。

通过这个例子，我们可以理解到学习科学是需要进行实验和观察的。只有通过实践，我们才能真正理解并应用所学的知识。

一本通 例6.8 进制转换

题目描述：

输入两个正整数 $a$ 和 $n$，将 $a$ 转换为 $n$ 进制数输出。

输入格式：

输入共两行，第一行包含两个正整数 $a$ 和 $n$，分别表示十进制整数和目标进制数 $(2≤n≤16)$。

第二行为 $a$ 的 $10$ 进制表示，$a$ 是一个非负整数，且不超过 $2^{31}-1$。

输出格式：

输出 $a$ 的 $n$ 进制表示。

注意：输出的每个字符必须是大写字母。如果 $a$ 为 $0$，输出 $0$。

输入样例：

10 2
7

输出样例：

$111$

算法1：

将十进制转为目标进制，按照取余数的方法，将余数从后向前排列即可。

C++ 代码：

#include <iostream>
#include <stack>

using namespace std;

stack<int> s;

int main()
{
    int a, n;
    cin >> a >> n;

    if (a == 0)
    {
        cout << 0 << endl;
        return 0;
    }

    while (a)
    {
        s.push(a % n);
        a /= n;
    }

    while (!s.empty())
    {
        int t = s.top();
        if (t < 10) cout << t;
        else cout << char(t - 10 + 'A');
        s.pop();
    }

    return 0;
}

Python 代码：

a, n = map(int, input().split())

if a == 0:
    print(0)
else:
    s = []
    while a:
        s.append(a % n)
        a //= n

    s.reverse()
    for x in s:
        if x < 10:
            print(x, end="")
        else:
            print(chr(ord('A') + x - 10), end="")

时间复杂度：$O(log_2 a)$

空间复杂度：$O(log_2 a)$