Maximum sum :)

Правка en1, от invoker._, 2022-06-04 14:34:39

So here is the problem

Let array A = { a1,a2,a3,...an} postitive integers

F(i,j) = min(ai,ai+1,....,aj) * (i-j+1);

Find the maximum value of F(i,j) for any I and J.

Example: A = {5,3,1,1}

(I = 1 J = 2) : SUM = 6

Example: A = {3,1,3,1,2}

(I = 1 J = 5) : SUM = 5

I came up with a DP approach but it gets very complex when 2 states return the same profit

my soln:

pair<int,int> dp(int i,vector<int>&arr)
{	
	if(i==arr.size()-1)
		return {arr[i],1};
	else
	{	pair<int,int>p = dp(i+1,arr);
		int v1 = min(p.first,arr[i])*(p.second+1);
		int v2 = arr[i];
		if(v1 > v2)
		{
			return {min(p.first,arr[i]),p.second+1};
		}
		else
		{
			return {arr[i],1};
		}
	}
}

This does not work for cases like {5,3,1,1}, it just gets very complex making it return multiple pairs EG: when ( V1 == v2)

Теги dp, help, arrays

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский invoker._ 2022-06-04 15:19:51 559
en1 Английский invoker._ 2022-06-04 14:34:39 868 Initial revision (published)