Subarray Removal

Time limit: 1000 ms
Memory limit: 128 MB

You are given an array of N integers. You should remove a non-emptysubarray of size at most N-1. Then you should compute the maximum sum subarray in the resulting array. Find out the maximum value you can get.

Standard input

The first line contains a single integer value N.

The second line contains N integers representing the elements of the array.

Standard output

The output should contain a single integer, the wanted answer.

Constraints and notes

• 2 ≤ N ≤ 100 000
• The elements of the array will be between -10^9 and 10^9

Input	Output	Explanation
5 10 -2 3 -10 5	16	We eliminate -10, and the remaining array is the maximum sum subarray : 10 -2 3 5.
7 -3 2 -1 5 -7 9 -10	15	We eliminate -7. The resulting array is: -3 2 -1 5 9 -10. The maximum sum subarray is : 2 -1 5 9  THIS CAN BE REDUCED AS A CLASSIC MAXIMUM SUBARRAY SUM PROBLEM , REMEMBER YOU ALWAYS NEED TO REMOVE A SEGMENT , SO FIRST CALCULATE THE PREFIX AND SUFFIX FOR EVERY i . NOW WE CHECK FROM THE BACK FOR REMOVING SEGMENTS ****SEE THE CODE******** #include<bits/stdc++.h> using namespace std; #define ll long long int int main() {  int n;  cin>>n;  string temp="";  for(int i=0;i<n;i++)  {    string s;    cin>>s;    sort(s.begin(),s.end());    temp+=s[0];  }  sort(temp.begin(),temp.end());  cout<<temp<<endl;  return 0; }