Press "Enter" to skip to content

Posts tagged as “subarray”

花花酱 LeetCode 410. Split Array Largest Sum

Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

Examples:

Input:
nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

 

Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

C++ / DP

Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

 

花花酱 LeetCode 845. Longest Mountain in Array

Problem

题目大意:找出最长的山形子数组。

https://leetcode.com/problems/longest-mountain-in-array/description/

Let’s call any (contiguous) subarray B (of A) a mountain if the following properties hold:

  • B.length >= 3
  • There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

(Note that B could be any subarray of A, including the entire array A.)

Given an array A of integers, return the length of the longest mountain.

Return 0 if there is no mountain.

Example 1:

Input: [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

Example 2:

Input: [2,2,2]
Output: 0
Explanation: There is no mountain.

 

Note:

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000

Solution: DP

Three passes

Time complexity: O(n)

Space complexity: O(n)

C++

One pass

Time complexity: O(n)

Space complexity: O(1)

 

花花酱 LeetCode 413. Arithmetic Slices

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

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)

Solution 1: Combined

C++

Time complexity: O(n)

Space complexity: O(1)

Related Problems:

 

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

题目大意:问一个数组中有多少个子数组的最大元素值在[L, R]的范围里。

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Solution 1:

C++

Solution 2: One pass

C++

 

花花酱 LeetCode 654. Maximum Binary Tree

 

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Idea:

Recursion

Solution:

With copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(nlogn) ~ O(n^2)

running time 79ms

Without copy

Time complexity: O(nlogn) ~ O(n^2)

Space complexity: O(logn) ~ O(n)

running time 66ms