DON'T SUBMIT CODING UNTIL MCQ POST ARRIVES
IN MEAN TIME CLICK ON ADS
PROBLEM 1:
Problem statement
Given an array arr of N integers. Find the contiguous sub-array with maximum sum.
Input Format
First line of input contains integer n. Next line of input contains n space separated integers which are
the elements of the array.
Constraints
1 ≤ N ≤ 106
-10^7 ≤ Ai <= 10^7
Output Format
Print the sum of subarray with maximum sum.
C++ CODE:
#include<iostream>
#include<climits>
using namespace std;
int maxSubArraySum(int a[], int size)
{
int max_so_far = INT_MIN, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
int main()
{int n;cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int max_sum = maxSubArraySum(a, n);
cout << max_sum;
return 0;
}
PROBLEM 2:
Problem statement
Given a NxN matrix of positive integers. There are only three possible moves from a cell Matrixr.
Matrix r+1 Matrix r+1 Matrix r+1
Starting from any column in row 0, return the largest sum of any of the paths up to row N-1.
Input Format
First line of input contains 'N', the size of N*N matrix.Next N line contains N integers each which are the
eements of matrix.
Constraints
1 ≤ N ≤ 100 1 ≤ Matrixi ≤ 1000
Output Format
Print the highest maximum path sum.
C++ CODE:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
long long dp[21][21];
long long find(int x,int y,vector<vector<int> >&v){
long long ans = 0;
if(x==v.size() || y == v.size() || y<0){
return 0;
}
if(dp[x][y] != -1)return dp[x][y];
ans = max(ans,find(x+1,y,v)+v[x][y]);
ans = max(ans,find(x+1,y-1,v)+v[x][y]);
ans = max(ans,find(x+1,y+1,v)+v[x][y]);
dp[x][y] = ans;
return ans;
}
int main() {
int n;
cin>>n;
vector<vector<int> > v(n,vector<int>(n,0));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>v[i][j];
}
}
memset(dp,-1,sizeof(dp));
long long ans = 0;
for(int i=0;i<n;i++){
ans = max(ans,find(0,i,v));
}
cout<<ans<<endl;
return 0;
}
PROBLEM 3:
Problem statement
Suppose you have N eggs and you want to determine from which floor in a K-floor building you can
drop an egg such that it doesn't break. You have to determine the minimum number of attempts you
need in order find the critical floor in the worst case while using the best strategy.There are few rules
given below.
An egg that survives a fall can be used again. A broken egg must be discarded. The effect of a fall is the
same for all eggs. If the egg doesn't break at a certain floor, it will not break at any floor below. If the
eggs breaks at a certain floor, it will break at any floor above.
Input Format
First line of input contains N. Second line of input contains K.
Constraints
1<=N<=200 1<=K<=200
Output Format
Print the minimum number of attempts you need in order to find the critical floor.
C++ CODE:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int func(int N, int K, vector<vector<int>>&dp)
{
if(N == 1)
return K;
if(K == 1 || K == 0)
return K;
int mn = INT_MAX;
for(int i = 1; i <= K; i++)
{
if(dp[N-1][i-1] == -1)
dp[N-1][i-1] = func(N-1, i-1, dp);
if(dp[N][K-i] == -1)
dp[N][K-i] = func(N, K-i, dp);
mn = min(mn, max(dp[N-1][i-1], dp[N][K-i]));
}
return 1+mn;
}
int main() {
int N; int K;
cin >> N;
cin >> K;
vector<vector<int>>dp(N+1, vector<int>(K+1, -1));
cout << func(N, K, dp) << endl;
return 0;
}
Post a Comment