# Sub-array lintcode Problem Set Summary C++

• Matrix Zigzag Traversal

Given a matrix:

[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10, 11, 12]
]
return [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]

Solution :

``````class Solution {
public:
/**
* @param matrix: a matrix of integers
* @return: a vector of integers
*/
vector<int> printZMatrix(vector<vector<int>> &matrix) {
vector<int> zigzag;
const int m = matrix.size()-1, n = matrix[0].size()-1;
for (int i = 0; i <= m + n; ++i) {
if (i & 1) {
for (int x = 0; x <= i; x++) {
if ((x <= m) && (i - x <= n)) {
zigzag.emplace_back(matrix[x][i-x]);
}
}
} else {
for (int x = i; x >= 0; x--) {
if ((x <= m) && (i-x) <= n) {
zigzag.emplace_back(matrix[x][i-x]);
}
}
}
}
return zigzag;
}
};
``````

Sub-Array Sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.

Given [-3, 1, 2, -3, 4], return [0, 2] or [1, 3].

Solution

``````class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
*          and the index of the last number
*/
vector<int> subarraySum(vector<int> nums) {
unordered_map<int, int> table;
/** the start position **/
table[0] = -1;
for (int i = 0, sum = 0; i < nums.size(); ++i) {
sum += nums[i];
if (table.find(sum) != table.end()) {  // Already exists.
return {table[sum] + 1, i};
}
table[sum] = i;
}
return {};
}
};
``````

So how about extending to matrix ?

Submatrix Sum

Given an integer matrix, find a submatrix where the sum of numbers is zero. Your code should return the coordinate of the left-up and right-down number.

``````class Solution {
public:
/**
* @param matrix an integer matrix
* @return the coordinate of the left-up and right-down number
*/
vector<vector<int>> submatrixSum(vector<vector<int>>& matrix) {
vector<vector<int>> result;
if (matrix.size() == 0)  return result;
int rows = matrix.size(), cols = matrix[0].size();
vector<vector<int>> sum(rows + 1, vector<int>(cols + 1, 0));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum[i+1][j+1] = matrix[i][j] + sum[i+1][j] + sum[i][j+1] - sum[i][j];
}
}
unordered_map<int, int> dict;
for (int i = 0; i < rows; i++) {
for (int j = i + 1; j <= rows; j++) {
dict.clear();
dict[0] = 0;
for(int k = 1; k <= cols; k++) {
int diff = sum[j][k] - sum[i][k];
if(dict.find(diff) != dict.end()) {
result.push_back({i, dict[diff]});
result.push_back({ j - 1, k - 1});
return result;
}
dict[diff] = k;
}
}
}
return result;
}
};

``````

Maximum Subarray

``````class Solution {
public:
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
int maxSubArray(vector<int> nums) {
int max_sum = INT_MIN, sum = 0;
for (const auto& i : nums) {
sum += i;
max_sum = max(max_sum, sum);
sum = max(sum, 0);
}
return max_sum;
}
};

``````

Minimum Subarray

Solution

``````class Solution {
public:
/**
* @param nums: a list of integers
* @return: A integer denote the sum of minimum subarray
*/
int minSubArray(vector<int> nums) {
int min_sum = INT_MAX, sum = 0;
for (auto& i : nums) {
sum += i;
min_sum = min(min_sum, sum);
if (sum > 0) {
sum = 0;
}
}
return min_sum;
}
};
``````

Maximum Subarray 2

Given an array of integers, find two non-overlapping subarrays which have the largest sum. The number in each subarray should be contiguous. Return the largest sum.

For given [1, 3, -1, 2, -1, 2], the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2], they both have the largest sum 7.

``````class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
int maxTwoSubArrays(vector<int> nums) {
int n = nums.size();
vector<int> max_LR(n);
vector<int> max_RL(n);
int max_LR_sum = INT_MIN, LR_sum = 0;
for(int i = 0; i < n; i++) {
LR_sum += nums[i];
max_LR_sum = max(max_LR_sum, LR_sum);
max_LR[i] = max_LR_sum;
LR_sum = max(LR_sum, 0);
}

int max_RL_sum = INT_MIN, RL_sum = 0;
for(int i = n - 1; i >= 0; i--) {
RL_sum += nums[i];
max_RL_sum = max(max_RL_sum, RL_sum);
max_RL[i] = max_RL_sum;
RL_sum = max(RL_sum, 0);
}
int max_sum = INT_MIN;
for(int i = 0; i < n - 1; i++) {
max_sum = max(max_sum, max_LR[i] + max_RL[i+1]);
}
return max_sum;
}
};

``````

Maximum Subarray 3

Given an array of integers and a number k, find k non-overlapping subarrays which have the largest sum.

典型划分类动态规划
localMax[i][k] 表示前i个数，取k个子数组，包含第i个数的Maximum Sum
globalMax[i][k] 表示前i个数，取k个子数组，可以不包含第i个数的Maximum Sum
状态转移方程

localMax[i][k] = max(localMax[i - 1][k] + nums[i - 1], globalMax[i - 1][k - 1] + nums[i - 1])
globalMax[i][k] = max(globalMax[i - 1][k], localMax[i][k])

``````class Solution {
public:
int maxSubArray(vector<int>& nums, int k) {
int n = nums.size();
vector<vector<long>> local(n+1, vector<long>(k+1, INT_MIN));
vector<vector<long>> global(n+1, vector<long>(k+1, INT_MIN));
for (int i = 0; i < n+1; i++) local[i][0] = global[i][0] = 0;
for (int i = 1; i < n+1; i++) {
local[i][0] = global[i][0] = 0;
for(int j = 1; j < k+1; j++) {
local[i][j] = max(local[i-1][j] + nums[i-1], global[i-1][j-1] + nums[i-1]);
global[i][j] = max(global[i-1][j], local[i][j]);
}
}
return global[n][k];
}
};

``````
``````class Solution {
public:
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
int maxSubArray(vector<int> nums, int k) {
const int n = nums.size();

// sums[x][y] means the max sum in range [0, x - 1] with k non-overlapping subarrays
vector<vector<int>> sums(n + 1, vector<int>(k + 1, INT_MIN));

for (int i = 0; i <= n; ++i) {
sums[i][0] = 0;
}

for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= min(i, k); ++j) {
sums[i][j] = sums[i - 1][j];
int sum = 0, max_sum = INT_MIN;
for (int p = i; p > j - 1; --p) {
sum += nums[p - 1];
max_sum = max(max_sum, sum);
sum = max(0, sum);
// max sum in range[0, i - 1] with j subarrays equals to
// max sum in max(range [0, p - 2] with j - 1 subarrys plus
// max sum in range [p - 1, i - 1] with 1 subarray
sums[i][j] = max(sums[i][j], sums[p - 1][j - 1] + max_sum);
}
}
}

return sums[n][k];
}
};
``````

Maximum Sub-Array Difference

Given an array with integers.Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.Return the largest difference.

``````class Solution {
public:
/**
* @param nums: A list of integers
* @return: An integer indicate the value of maximum difference between two
*          Subarrays
*/
int maxDiffSubArrays(vector<int> nums) {
int n = nums.size();
vector<int> max_LR(n), min_LR(n);
vector<int> max_RL(n), min_RL(n);

// Compute the max sum of subarray from left to right.
int max_LR_sum = INT_MIN, LR_sum = 0;
for (int i = 0; i < n; ++i) {
LR_sum += nums[i];
max_LR_sum = max(max_LR_sum, LR_sum);
max_LR[i] = max_LR_sum;
if (LR_sum < 0) {
LR_sum = 0;
}
}

// Compute the min sum of subarray from left to right.
int min_LR_sum = INT_MAX;
LR_sum = 0;
for (int i = 0; i < n; ++i) {
LR_sum += nums[i];
min_LR_sum = min(min_LR_sum, LR_sum);
min_LR[i] = min_LR_sum;
if (LR_sum > 0) {
LR_sum = 0;
}
}

// Compute the max sum of subarray from right to left.
int max_RL_sum = INT_MIN, RL_sum = 0;
for (int i = n - 1; i >= 0; --i) {
RL_sum += nums[i];
max_RL_sum = max(max_RL_sum, RL_sum);
max_RL[i] = max_RL_sum;
if (RL_sum < 0) {
RL_sum = 0;
}
}

// Compute the min sum of subarray from right to left.
int min_RL_sum = INT_MAX;
RL_sum = 0;
for (int i = n - 1; i >= 0; --i) {
RL_sum += nums[i];
min_RL_sum = min(min_RL_sum, RL_sum);
min_RL[i] = min_RL_sum;
if (RL_sum > 0) {
RL_sum = 0;
}
}

// Compute the max diff of two non-overlapping subarrays.
int max_diff = 0;
for (int i = 0; i < n - 1; ++i) {
max_diff = max(max_diff, abs(max_LR[i] - min_RL[i+1]));
max_diff = max(max_diff, abs(min_LR[i] - max_RL[i+1]));
}

return max_diff;
}
};
``````

Subarray Sum Closest

Given an integer array, find a subarray with sum closest to zero. Return the indexes of the first number and last number.

Given [-3, 1, 1, -3, 5], return [0, 2], [1, 3], [1, 1], [2, 2] or [0, 4].

Solution :

``````class Solution {
public:
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
*          and the index of the last number
*/
vector<int> subarraySumClosest(vector<int> nums){
vector<pair<int, int> > acc;
acc.push_back(make_pair(0, -1));
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
acc.push_back(make_pair(sum, i));
}
sort(acc.begin(), acc.end());
int min_abs = INT_MAX, a, b, tmp;
for (int i = 1; i < acc.size(); ++i) {
tmp = abs(acc[i].first - acc[i-1].first);
if (min_abs >= tmp) {
min_abs = tmp;
a = acc[i-1].second;
b = acc[i].second;
}
}
vector<int> res;
res.push_back(min(a, b) + 1);
res.push_back(max(a, b));
return res;
}
};

``````

Maximum Product Subarray

``````class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.empty()) return 0;
int result = nums[0], global_min = nums[0], global_max = nums[0];
for (int i = 1; i < nums.size(); i++) {
int local_min = global_min, local_max = global_max;
global_max = max(max(nums[i], local_max * nums[i]), local_min * nums[i]);
global_min = min(min(nums[i], local_max * nums[i]), local_min * nums[i]);
result = max(result, global_max);
}
return result;
}
};
``````

Continuous Subarray Sum
Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

``````class Solution {
public:
/**
* @param A an integer array
* @return  A list of integers includes the index of
*          the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int>& A) {
if (A.empty()) {
return {-1, -1};
}

int curr_sum = 0;
int max_sum = 0;
vector<int> result{0, 0};
int start = 0;
for (int j = 0; j < A.size(); ++j) {
curr_sum += A[j];

if (curr_sum > max_sum) {
max_sum = curr_sum;
result[0] = start, result[1] = j;
}

if (curr_sum < 0) {
start = j+1;
curr_sum = 0;
}
}

return result;
}
};

``````

Continuous Subarray Sum 2

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)
Example Give [-3, 1, 3, -3, 4], return [1,4].

``````class Solution {
public:
/**
* @param A an integer array
* @return  A list of integers includes the index of
*          the first number and the index of the last number
*/
vector<int> continuousSubarraySumII(vector<int>& A) {
vector<int> result{-1, -1};
int max_sum = numeric_limits<int>::min();
int total = 0;

// Non-circular subarray.
int sum = 0;
int start = 0, end = 0;
for (int i = 0; i < A.size(); ++i) {
total += A[i];
if (sum < 0) {
sum = A[i];
start = end = i;
} else {
sum += A[i];
end = i;
}
if (sum >= max_sum) {
max_sum = sum;
result[0] = start;
result[1] = end;
}
}

// Circular subarray.
sum = 0;
start = 0, end = -1;
for (int i = 0; i < A.size(); ++i) {
if (sum > 0) {
sum = A[i];
start = end = i;
} else {
sum += A[i];
end = i;
}
if (total - sum > max_sum && !(start == 0 && end == A.size() - 1)) {
max_sum = total - sum;
result[0] = (end + 1) % A.size();
result[1] = (start - 1) % A.size();
}
}

return result;
}
};
``````

The key are the following lines :

``````        curr_sum = 0;
start = 0, end = -1;

for (int i = 0; i < A.size(); i++) {
curr_sum += A[i];
if (total - sum > max_sum && (!(start == 0 && end == A.size() - 1))) {
max_sum = total - sum;
result[0] = (end + 1) % A.size();
result[1] = (start - 1) % A.size();
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.