[LeetCode] Medium - 1043. Partition Array for Maximum Sum

Source From Here
Question
Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning.

Example 1:

Input: A = [1,15,7,9,2,5,10], K = 3
Output: 84
Explanation: A becomes [15,15,15,9,10,10,10]

Note:

* 1 <= K <= A.length <= 500
* 0 <= A[i] <= 10^6

Solution

Naive Approach (DP)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def maxSumAfterPartitioning(self, A, K):  
3.         # 0) Initialization  
4.         #    best_a is used to keep past computation result  
5.         #    best_a[i] is to keep local optimal result of A[0:i-1]  
6.         best_a = [0] * len(A)  
7.         best_a[0] = A[0]  
8.   
9.         # 1) Iteratively fill the best_a with local optimal result  
10.         #    best_a[0] = A[0]  
11.         #    best_a[1] = max(best_a[0] + A[1], max(A[0:2]) * 2)  
12.         #    best_a[2] = max(best_a[1] + A[2], best_a[0] + max(A[1:3]) * 2, max(A[0:3]) * 3)  
13.         #    ...  
14.         #    best_a[n] = max(best_a[n-1] + A[n], best_a[n-2] + max(A[n-1:n+1]) * 2, ..., max(A[n-K+1:n+1]) * K)  
15.         for i in range(1, len(A)):  
16.             max_v = 0  
17.             for j in range(i, max(-1, i-K), -1):  
18.                 sa = A[j:i+1]  
19.                 v = best_a[j-1] + max(sa) * len(sa)  
20.                 if v > max_v:  
21.                     max_v = v  
22.   
23.             best_a[i] = max_v  
24.   
25.         # 2) The global optimal result is kept in last element  
26.         return best_a[-1]  

Supplement
* 花花酱 LeetCode 1043. Partition Array for Maximum Sum - 刷题找工作 EP250

[Linux 常見問題] grep + add time out after some time if not find the relevant match

Source From Here
Question
I use the following command syntax to search params in my script

# grep -qsRw -m1 "any_param" /dir/..../

Some times the search take a very long time. The question is how to add time out to grep command. For example after 20 seconds grep will break out

How-To
There is a Linux command timeout that can do this for you. For example:

# time grep -R -m 1 -e "pattern to search" Github/

real 0m3.627s
user 0m1.824s
sys 0m1.798s

# echo $?
1 // Return code from command grep

# timeout 2s grep -R -m 1 -e "pattern to search" Github/ // Force the grep to timeout after 2 second
# echo $?
124 // Return code from command timeout

[LeetCode] Medium - 1130. Minimum Cost Tree From Leaf Values

Source From Here
Question
Given an array arr of positive integers, consider all binary trees such that:

* Each node has either 0 or 2 children;
* The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
* The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:

view plaincopy to clipboardprint?

1. Input: arr = [6,2,4]  
2. Output: 32  
3. Explanation:  
4. There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.  
5.   
6.     24            24  
7.    /  \          /  \  
8.   12   4        6    8  
9. /  \               / \  
10. 6    2             2   4  

Constraints:

* 2 <= arr.length <= 40
* 1 <= arr[i] <= 15
* It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Solution
Naive Solution

view plaincopy to clipboardprint?

1. #!/usr/bin/env python  
2. import sys  
3.   
4. class Solution:  
5.     def mctFromLeafValues(self, arr):  
6.         sum_of_non_leaf = 0  
7.   
8.         print("### arr={}".format(arr))  
9.         def look_4_min(arr):  
10.             mi = 0  
11.             mv = arr[0] * arr[1]  
12.             for i in range(1, len(arr)-1):  
13.                 v = arr[i] * arr[i+1]  
14.                 if v < mv:  
15.                     mi = i  
16.                     mv = v  
17.   
18.             rst = (mi, max(arr[mi], arr[mi+1]), mv)  
19.             print('\t{}'.format(rst))  
20.             return rst  
21.   
22.         while len(arr) > 2:  
23.             print("{}: {}".format(arr, sum_of_non_leaf))  
24.             mi, mx, mv = look_4_min(arr)  
25.             sum_of_non_leaf += mv  
26.             arr[mi:mi+2] = [mx]  
27.   
28.         print("{}: {}".format(arr, sum_of_non_leaf))  
29.         sum_of_non_leaf += arr[0] * arr[1]  
30.   
31.         print("[]: {}".format(sum_of_non_leaf))  
32.         return sum_of_non_leaf  
33.   
34. if __name__ == '__main__':  
35.     s = Solution()  
36.     for arr, aw in [  
37.                 ([6,2,4], 32),  
38.                 ([15,13,5,3,15], 500),  
39.                 ([1,2,3,4], 20),  
40.                 ([4,3,2,1], 20),  
41.                 ([1,3,4,2], 23),  
42.                 ([4,2,3,1], 21)  
43.                ]:  
44.         rel = s.mctFromLeafValues(arr)  
45.         assert aw == rel  
46.         print("")  

Execution result:

### arr=[6, 2, 4]
[6, 2, 4]: 0
(1, 4, 8)
[6, 4]: 8
[]: 32

### arr=[15, 13, 5, 3, 15]
[15, 13, 5, 3, 15]: 0
(2, 5, 15)
[15, 13, 5, 15]: 15
(1, 13, 65)
[15, 13, 15]: 80
(0, 15, 195)
[15, 15]: 275
[]: 500
...

Supplement
* 米开：LeetCode 1130. Minimum Cost Tree From Leaf Values

[NodeJS 文章收集] NodeJS accessing file with relative path

Source From Here
Question
It seemed like a straight forward problem. But I am not able to crack this. Within helper1.js I would like to access foobar.json (from config/dev/)

view plaincopy to clipboardprint?

1. root  
2.   -config  
3.    --dev  
4.     ---foobar.json  
5.   -helpers  
6.    --helper1.js  

Any help here would be great.

How-To
You can use the path module to join the path of the directory in which helper1.js lives to the relative path of foobar.json. This will give you the absolute path to foobar.json:

view plaincopy to clipboardprint?

1. var fs = require('fs');  
2. var path = require('path');  
3.   
4. var jsonPath = path.join(__dirname, '..', 'config', 'dev', 'foobar.json');  
5. var jsonString = fs.readFileSync(jsonPath, 'utf8');