筆試 | 字節跳動 最優連續子序列

字節跳動08.09筆試：最優連續子序列

給定一個長度為n的整數序列

輸入描述輸入的第一行為一個正整數n(n<=1e5)，表示序列的長度輸入的第二行為n個整數，依次給出了

做這個題之前我們先看看另外一個問題。給定一個長度為n的整數序列，找出其中一段連續子序列，使得該段連續子序列的和最大。這是一道經典的動態規劃-「最大子段和問題」。

對於最大子段和問題，假設

第二種，這個子序列包含

「邊界情況」，當

到這裡我們就可以很輕鬆的寫出最大子段和問題的解了。

轉到這個題上來，這個要求的是最大交替和。對於某一個元素

所以問題可以轉化為求兩個數組的最大子段和問題。第一個數組是

回味下這個題最關鍵的在於將問題轉化為求最大連續子段和問題。對於動態規劃問題，首先將大的問題劃分為多個小的子問題。類似題https://leetcode.com/problems/maximum-subarray/https://leetcode.com/problems/maximum-product-subarray/https://leetcode.com/problems/longest-turbulent-subarray/附上最大子段和代碼，聊表敬意

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> num(n);
    int ans = 0, tmp_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        if (tmp_sum > 0) tmp_sum += num[i];
        else tmp_sum = num[i];
        if (tmp_sum > ans) ans = tmp_sum;
    }
    cout << ans << endl;
    return 0;
}
歡迎關注我們，希望能夠在你秋招的過程中帶來一些幫助。面鯨，專注於網際網路求職經驗分享。
關注公眾號可添加小編微信加入面試交流&刷題群，與更多的小夥伴一起上岸