动态规划——最大连续子序列和¶

动态规划——最大连续子序列和¶

一维最大连续子序列和¶

LeetCode 53 Maximum Subarray
HDU 1024 Max Sum Plus Plus

设 $d[i]$ 表示以序列中 $s[i]$ 结尾的最大连续子序列和，状态转移方程： $$ d[i] = \max{d[j - 1] + s[i], s[i]} \quad 1 \leq i \leq n \ target = \max(d[i]) $$

int maxSubArray(vector<int>& nums) {
    int tmpSum, maxSum;
    tmpSum = maxSum = nums[0];

    for (int i = 1; i < nums.size(); ++i){
        tmpSum = max(tmpSum + nums[i], nums[i]);
        maxSum = max(maxSum, tmpSum);
    }

    return maxSum;
}

最大子矩阵（二维情形）¶

一本通-1282：最大子矩阵

这道题还可以和二分进行结合，比如求二维矩阵里子矩阵和不超过K的最大和。

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如，如下4 × 4的矩阵

0  -2 -7  0
9  2 -6  2
-4  1 -4  1
-1  8  0 -2

的最大子矩阵是

 9 2
-4 1
-1 8

这个子矩阵的大小是15。

相当于把多行压缩成一行，于是转化成求一维的最大连续子数组和。

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int> > matrix(105, vector<int>(105));
vector<int> d(105), tmp(105);

int largestCotinuousSequenceSum()
{
    fill(d.begin(), d.begin() + n, 0);

    int tmpSum = tmp[0], maxSum = tmp[0];
    for (int i = 1; i < n; ++i) {
        tmpSum = max(tmpSum + tmp[i], tmp[i]);
        maxSum = max(maxSum, tmpSum);
    }

    return maxSum;
}

int largestSubmatrixSum()
{
    int res = INT_MIN;
    for (int i = 0; i < n; ++i) {
        fill(tmp.begin(), tmp.begin() + n, 0);
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                tmp[k] += matrix[j][k];
            }
            res = max(res, largestCotinuousSequenceSum());
        }
    }

    return res;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> matrix[i][j];
        }
    }

    cout << largestSubmatrixSum() << endl;

    return 0;
}

最大乘积子数组¶

LeetCode 152.乘积最大子数组
UVA 11059 Maximum Product

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int res = nums[0];
        int large = nums[0];
        int small = nums[0];

        for (int i = 1; i < n; ++i) {
            int tmpMax = large, tmpMin = small;
            large = max(max(tmpMax * nums[i], tmpMin * nums[i]), nums[i]);
            small = min(min(tmpMax * nums[i], tmpMin * nums[i]), nums[i]);
            res = max(res, large);
        }

        return res;
    }
};

典型题目：

LeetCode 53 Maximum Subarray
HDU 1024 Max Sum Plus Plus
LeetCode 152.乘积最大子数组
UVA 11059 Maximum Product