Question

leetcode A tourism company is providing boat tours on a river with n consecutive segments. According to previous experience, the profit they can make by providing boat tours on segment $i$ is known as $a_i$. Here, $a_i$ could be positive (they earn money), negative (they lose money), or zero. Because of the administration convenience, the local community requires that the tourism company do their boat tour business on a contiguous sequence of the river segments (i.e., if the company chooses segment $i$ as the starting segment and segment $j$ as the ending segment, all the segments in between should also be covered by the tour service, no matter whether the company will earn or lose money). The company's goal is to determine the starting segment and ending segment of boat tours along the river, such that their total profit can be maximized. Design a dynamic programming algorithm to achieve this goal and analyze its runtime.

Answer 1

Answer:

OPT[i] : segment that end in i with largest amount N

OPT[0] = 0

OPT[i] = max{OPT[i-1] + ai, 0}

for i from 1 to n

if (OPT[i] > max) {

max = OPT[i]

max_i = i

}

count = 0

for i from max_i to 1

count +=a[i]

if (count== max) {

start = i ;

break;

}