Posts tagged as “reduction”

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

By zxi on September 15, 2019

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int kConcatenationMaxSum(vector<int>& arr, int k) {

constexpr int kMod = 1e9 + 7;

auto maxSum = [&arr](int r) {

long sum = 0;

long ans = 0;

for (int i = 0; i < r; ++i) {

for (long a : arr) {

sum = max(0L, sum += a);

ans = max(ans, sum);

}

return ans;

};

if (k < 3) return maxSum(k) % kMod;

long ans1 = maxSum(1);

long ans2 = maxSum(2);

long sum = accumulate(begin(arr), end(arr), 0L);

return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;

}

};

花花酱 LeetCode 413. Arithmetic Slices

By zxi on March 17, 2018

题目大意：返回所有子数组中等差数列的个数。

Problem

https://leetcode.com/problems/arithmetic-slices/description/

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], …, A[Q – 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

Solution 0: Reduction

Reduce the problem to # of all 1 sub arrays.

B[i – 2] = is_slice(A[i], A[i+1], A[i+2])

Time Complexity: O(n)

Space Complexity: O(n)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

if (A.size() < 3) return 0;

vector<int> B(A.size() - 2, 0);

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1])

B[i - 2] = 1;

}

return all1SubArrays(B);

}

private:

// return number of arrays whose values are all ones.

int all1SubArrays(const vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 0; i < A.size(); ++i)

if (A[i]) sum += ++curr;

else curr = 0;

return sum;

}

};

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int numberOfArithmeticSlices(vector<int>& A) {

int sum = 0;

int curr = 0;

for (int i = 2; i < A.size() ; ++i) {

if (A[i - 1] - A[i - 2] == A[i] - A[i - 1]) {

sum += ++curr;

} else {

curr = 0;

}

return sum;

}

};

Related Problems:

花花酱 LeetCode 795. Number of Subarrays with Bounded Maximum

花花酱 LeetCode 121. Best Time to Buy and Sell Stock

By zxi on December 22, 2017

题目大意: 给你一只股票每天的价格，如果只能做一次交易（一次买进一次卖出）问你最多能赚多少钱。

Problem:

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]

Output: 0

In this case, no transaction is done, i.e. max profit = 0.

Idea:

Solution 1:

C++

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

const int n = prices.size();

if (n < 1) return 0;

vector<int> min_prices(n);

vector<int> max_profit(n);

min_prices[0] = prices[0];

max_profit[0] = 0;

for (int i = 1; i < n; ++i) {

min_prices[i] = min(min_prices[i - 1],

prices[i]);

max_profit[i] = max(max_profit[i - 1],

prices[i] - min_prices[i - 1]);

}

return max_profit[n - 1];

}

};

C++ / reduce to maximum subarray

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int maxProfit(vector<int>& prices) {

int n = prices.size();

if (n < 2) return 0;

vector<int> gains(n - 1, 0);

for (int i = 1; i < n; ++i)

gains[i - 1] = prices[i] - prices[i - 1];

return max(0, maxSubArray(gains));

}

private:

// From LC 53. Maximum Subarray

int maxSubArray(vector<int>& nums) {

vector<int> f(nums.size());

f[0] = nums[0];

for (int i = 1; i < nums.size(); ++i)

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

return *std::max_element(f.begin(), f.end());

}

};

Related Problems:

花花酱 LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

花花酱 LeetCode 740. Delete and Earn

By zxi on December 5, 2017

Problem:

Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete everyelement equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

Example 1:

Input: nums = [3, 4, 2]

Output: 6

Explanation:

Delete 4 to earn 4 points, consequently 3 is also deleted.

Then, delete 2 to earn 2 points. 6 total points are earned.

Example 2:

Input: nums = [2, 2, 3, 3, 3, 4]

Output: 9

Explanation:

Delete 3 to earn 3 points, deleting both 2's and the 4.

Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.

9 total points are earned.

Note:

The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].

Idea:

Reduce the problem to House Robber Problem

Key observations: If we take nums[i]

We can safely take all of its copies.
We can’t take any of copies of nums[i – 1] and nums[i + 1]

This problem is reduced to 198 House Robber.

Houses[i] has all the copies of num whose value is i.

[3 4 2] -> [0 2 3 4], rob([0 2 3 4]) = 6

[2, 2, 3, 3, 3, 4] -> [0 2*2 3*3 4], rob([0 2*2 3*3 4]) = 9

Time complexity: O(n+r) reduction + O(r) solving rob = O(n + r)

Space complexity: O(r)

r = max(nums) – min(nums) + 1

Time complexity: O(n + r)

Space complexity: O(r)

Solution:

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

int deleteAndEarn(vector<int>& nums) {

if (nums.empty()) return 0;

const auto range = minmax_element(nums.begin(), nums.end());

const int l = *(range.first);

const int r = *(range.second);

vector<int> points(r - l + 1, 0);

for (const int num : nums)

points[num - l] += num;

return rob(points);

}

private:

// From LeetCode 198. House Robber

int rob(const vector<int>& nums) {

int dp2 = 0;

int dp1 = 0;

for (int i = 0; i < nums.size() ; ++i) {

int dp = max(dp2 + nums[i], dp1);

dp2 = dp1;

dp1 = dp;

}

return dp1;

}

};

Related Problem:

花花酱 LeetCode 198. House Robber