Ask Question
11 May, 15:04

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.

+5
Answers (1)
  1. 11 May, 16:03
    0
    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;

    }
Know the Answer?
Not Sure About the Answer?
Find an answer to your question ✅ “leetcode A tourism company is providing boat tours on a river with n consecutive segments. According to previous experience, the profit ...” in 📘 Computers and Technology if you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers