h***o
发帖数: 1494 | 1 Input:
1. an array of characters
2. a bunch of scores, for each
a. start (start position in the array)
b. end (end position in the array)
c. score (score is not related to the content of the substring or
length of the substring)
Scores could be overlapped.
Output:
all scores (there is no overlap on them) that have the maximum sum.
For example
Input:
"abcdedfhijk"
start: 1 end: 3 score: 5
start: 0 end: 10 score: 8
start: 5 end:6 score 4
Output:
start: 1 end: 3 score: 5
start: 5 end:6 score 4
Provide algorithm which is not brute force. |
x***y
发帖数: 633 | 2 This is the same as the job selection DP problem, first sort according to
the end time, and then DP. |
p********7
发帖数: 549 | |
h***o
发帖数: 1494 | 4
每一个substring有一个score, 但是substring 会overlap。找出所有的不overlap的
substring, 使得他们的sum of scores 最大。
【在 p********7 的大作中提到】
: 没看懂题，不知道string和答案有什么关系
|
E********a
发帖数: 124 | 5 I think so
【在 x***y 的大作中提到】
: This is the same as the job selection DP problem, first sort according to
: the end time, and then DP.
|
h***o
发帖数: 1494 | |
b********h
发帖数: 119 | |
h**6
发帖数: 4160 | |
h***o
发帖数: 1494 | |
a*******8
发帖数: 2299 | |
