Given an array m[ ] of npositive numbers.
Find the largest possible sum of elements of a special array ans[ ] that can be generated using the following condition on given array m[ ].
ans[i]<=m[i] for 0<=i<n
A special array is defined as the array which does not hold the following condition:
ans[j]>ans[i]<ans[k] where 0<=j<i<k<n
Example:
N = 5 m[ ] = {1,5,3,5,4}
Output:16
Explanation: The special array will be [1,3,3,5,4] with sum = 16, which is maximum. No other special array can achieve higher sum.
Can someone tell me the right solution for this problem:
This was my solution:
class Solution {
public :
long long specialSum(vector m, int n)
{
if(n<=2)return accumulate(m.begin(), m.end(), 0);
long long sum=m[0];
for(int i=1;i<n-1;i++)
{
if((m[i]<m[i-1]) and (m[i]<m[i+1]))
{
if(m[i-1]>=m[i+1])
{
// sum-=m[i+1]-m[i];
m[i+1]=m[i];
}
else
{
long long t=m[i-1]-m[i];
sum-=t;
}
}
sum+=m[i];
}
sum+=m[n-1];
return sum;
}
};