Solve to Win
You are preparing for a national-level coding competition and you want to make it to the last round now.
As part of your preparation, your cousin John has come up with a real-time problem statement, so that you could help him with the solution.
In this, John is planning to start a business across N cities. As initial investments consider all the investments are zero {cities[N]}. After a while, John has set a goal of returning the maximum profit value from all the cities based on the number of operational goals K specified. Along with that, John started partnering with different vendors who would also lend some investment amount for each of the operations.
You will have to help john find the maximum revenue gained across all the N cities based on the K operation(s) carried out.
Sample Input 1:
10 4
4 7 8
1 8 19
9 10 5
1 10 7
Sample Output:
34
Example 1
Input:
5 3
1 2 50
2 5 50
3 4 50
Output:
100
Example 2
Input:
10 4
4 7 8
1 8 19
9 10 5
1 10 7
Output:
34
Explanation:
John has planned to start his business across 10 cities.
No of operations John has set as a goal to get the maximum revenue is 4.
Initial investment across all the cities = 0 0 0 0 0 0 0 0 0 0
As first level of operation, investment across cities = 0 0 0 8 8 8 8 0 0 0
Partner-2 Chose to invest 19 points from cities[i] = 1 till cities[i] = 8.
Second level of opreration, investmen across cities = 19 19 19 27 27 27 27 19 0 0
Partner-3 to invest 5 point in cities[i]=9 & cities[i]=10.
Third level of operation, investment across the cities = 19 19 19 27 27 27 27 19 5 5
Partner-4 Chose to invest 7 point across the cities cities[i] = 1 till cities[i] = 10
Fourth level of operation, investment across all cities = 26 26 26 34 34 34 34 26 12 12
Now after comppleting all K{k = 4} operation across all the N cities{cities[10]}, the maximum revenue happened to be 34.
Therefore the output is 34.
Solution: In Java
import java.util.*;
import java.lang.*;
import java.io.*;
class CodeWindow
{
public static void main (String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
int[] cities = new int[n];
for(int i=0; i<k; i++) {
str = br.readLine().split(" ");
int a = Integer.parseInt(str[0]);
int b = Integer.parseInt(str[1]);
int profit = Integer.parseInt(str[2]);
for(int j=a-1; j<b; j++)
cities[j] += profit;
}
int max = cities[0];
for(int i=1; i<n; i++)
if(cities[i] > max)
max = cities[i];
System.out.println(max);
}
}
Also Checkout