Last Updated on March 10, 2022 by Ria Pathak
- Given an array of integers, find the indices of two numbers that sum up to the given target. For example –
Arr[] = {1, 2, 4 -3, 7}, and target = 6, we exactly one such occurrence return the indices of those elements.
Ans. The idea here is to use two pointer techniques after sorting the array. These two pointers work because we need to return two indices or find two sum elements whose sum is equal to the target and can be increased or decreased by changing the pointers. I and j are the two indices from left and right of the array respectively.arri+ arrj> target; j--; arri+ arrj< target; i++; arri+ arrj== target; return i,j;#include <bits/stdc++.h> using namespace std; vector<int> twoSum(vector<int>& nums, int target) { vector<pair<int,int> > v; for(int i = 0;i<nums.size();i++) v.push_back(make_pair(nums[i],i)); sort(v.begin(),v.end()); int i = 0, j = v.size()-1 ; while(i<j){ if(v[i].first + v[j].first > target) j--; if(v[i].first + v[j].first < target) i++; if(v[i].first + v[j].first == target) return {v[i].second,v[j].second}; } return {}; } int main() { // your code goes here int n; cin>>n; vector<int> v(n); for(int i =0;i<n;i++) cin>>v[i]; int target; cin>>target; vector<int> ans = twoSum(v,target); for(auto ele:ans) cout<<ele<<" "; return 0; } Output: 1 2 for given input. - Given an array of integers find the indices of three numbers that sum up to the given target. Find all those unique tuples.
Arr[] = {1, 2, 4 -3, 7}, and target = 3
Ans. The idea here is to use two pointer techniques after sorting the array. The only difference is we need to set a new target such for every element in the outer loop. Suppose every element in outer loop is arr[i] then new target= target-arr[i]. Then we can simply apply the same two pointer technique. These two pointers works because we need to return two indices or find two sum elements whose sum is equal to the target and can be increased or decreased by changing the pointers. I and j are the two indices from left and right of the array respectively.
for every arr[k], newtarget=target-arr[k]arri+ arrj> newtarget; j--; arri+ arrj< newtarget; i++; arri+ arrj== newtarget; return arri,arrj,arr[k];Ans.
#include <bits/stdc++.h> using namespace std; vector<vector<int>> threeSum(vector<int>& nums,int target) { if(nums.size()<3)return {}; set<vector<int> > sv; vector<vector<int> > ans; sort(nums.begin(),nums.end()); for(int i = 0;i<nums.size()-2;i++){ int newt = target - nums[i]; int j = i+1,k = nums.size()-1; while(j<k){ if(nums[j] + nums[k] > newt) k--; if(nums[j] + nums[k] < newt) j++; if(nums[j] + nums[k] == newt && j!=k) { sv.insert({nums[i],nums[j],nums[k]}); // if(j!=nums.size()-1 && k!=0 && j<k) j++;k--; } } } for(auto x : sv){ ans.push_back(x); } return ans; } int main() { // your code goes here int n; cin>>n; vector<int> v(n); for(int i =0;i<n;i++) cin>>v[i]; int target; cin>>target; vector<vector<int>> ans = threeSum(v,target); for(auto ele:ans) { cout<<ele[0]<<" "<<ele[1]<<" "<<ele[2]<<endl; } return 0; } -
Given an array of integers find the indices of four numbers that sum up to given target. Find all those unique 4 elements.
Arr[] = {1, 2, 4 -3, 7}, and target = 4
Output: -3 1 2 4
Ans.#include <bits/stdc++.h> using namespace std; vector<vector<int>> foursum(vector<int>& nums, int target) { if(nums.size()<4)return {}; sort(nums.begin(),nums.end()); vector<vector<int> > v; set<vector<int> > sv; for(int i = 0;i<nums.size()-3;i++){ int target1 = target - nums[i]; for(int j = i+1;j<nums.size()-2;j++){ int newt = target1 - nums[j]; int k = j+1,l=nums.size()-1; while(k<l){ if(nums[k] + nums[l] == newt) { sv.insert({nums[i],nums[j],nums[k],nums[l]}); k++;l--; } if(nums[k] + nums[l] > newt) l--; if(nums[k] + nums[l] < newt) k++; } } } for(auto x : sv) v.push_back(x); return v; } int main() { // your code goes here int n; cin>>n; vector<int> v(n); for(int i =0;i<n;i++) cin>>v[i]; int target; cin>>target; vector<vector<int>> ans = foursum(v,target); for(auto ele:ans) { cout<<ele[0]<<" "<<ele[1]<<" "<<ele[2]<<" "<<ele[3]<<endl; } return 0; } -
Given an array find the maximum sum of the subarray.
Arr = [-2 -2 4 -1 -2 1 5 -3]
Output: 4-1-2+1+5 = 7
Ans.#include <bits/stdc++.h> using namespace std; int kadane(int arr[], int n) { int globalmax= 0; int localmax= 0; for (int i = 0; i < n; i++) { localmax= localmax+ arr[i]; localmax= max(localmax, 0); globalmax= max(globalmax, localmax); } return globalmax; } int main() { int n; cin>>n; int arr[n]; for(int i = 0;i<n;i++) cin>>arr[i]; cout<<kadane(arr,n); return 0; } -
You are given the ability to shop as much as you can from a store. But you have limited capacity bag which can only hold weight up to w. There N items in the store. You have to take maximum valued items such that you can take those items home.
Input: 4(number of items)
1 2 4 5(weights of each item)
5 4 8 6 (values of each item)
Output: 13 =(5 + 8)
Ans.#include<iostream> using namespace std; int k(int* wt, int* val, int n, int w,int** dp) { if(n==0||w==0)return 0; if(dp[n][w]!=-1)return dp[n][w]; if(wt[n-1]<=w) { int ans = max(val[n-1]+k(wt,val,n-1,w-wt[n-1],dp),k(wt,val,n-1,w,dp)); dp[n][w] = ans; return ans; } if(wt[n-1]>w) { int ans = k(wt,val,n-1,w,dp); dp[n][w] = ans; return ans; } } int knapsack(int* weights, int* values, int n, int maxWeight){ int N = n; int w = maxWeight; int** dp = new int*[N+1]; for(int i = 0;i<n+1;i++) dp[i] = new int[w+1]; for(int i = 0;i<n+1;i++) for(int j = 0;j<w+1;j++) dp[i][j] = -1; return k(weights,values,N,w,dp); } int main(){ int n; cin >> n; int* weights = new int[n]; int* values = new int[n]; for(int i = 0; i < n; i++){ cin >> weights[i]; } for(int i = 0; i < n; i++){ cin >> values[i]; } int maxWeight; cin >> maxWeight; cout << knapsack(weights, values, n, maxWeight); } -
Given two strings write a program to find if one string is the substring of the other or not.
Input: WelcomeBack
Come
Output: 1
Ans.#include <bits/stdc++.h> using namespace std; int* lpsarray(string p) { int len = p.length(); int* lps = new int[len]; lps[0] = 0; int i = 1; int j = 0; while(i<len) { if(p[i]==p[j]){ lps[i] = j+1; j++; i++; } else { if(j!=0){ j = lps[j-1]; } else { lps[i] = 0; i++; } } } return lps; } bool isMatching(string str,string pattern) { int* lps = lpsarray(pattern); int lenstr = str.length(); int lenpattern = pattern.length(); int i = 0; int j = 0; while(i<lenstr && j<lenpattern) { if(str[i]==pattern[j]) { i++; j++; } else { if(j!=0){ j = lps[j-1]; } else { i++; } } } if(j==lenpattern)return true; return false; } int position(string str, string pattern) { int* lps = lpsarray(pattern); int lenstr = str.length(); int lenpattern = pattern.length(); int i = 0; int j = 0; while(i<lenstr && j<lenpattern) { if(str[i]==pattern[j]) { i++; j++; } else { if(j!=0){ j = lps[j-1]; } else { i++; } } } if(j==lenpattern)return (i - lenpattern); return -1; } int main() { string str; string pattern; cin>>str>>pattern; cout<<isMatching(str,pattern)<<endl; return 0; } - You are given a grid and you have to start from a position of top left. Each cells in the grid contains either health or poison. Health is denoted by positive integers while poison os denoted by negative integers. Whenever you come to a cell your health either increases or decreases depending upon the cell value. Now you have to reach the bottom right cell of the grid and if at any cell your health drops to zero you will loose. You have to find the minimum amount of health to start with so that you can reach the right most down cell.
Input: 1(test cases) 3 4 (dimensions of the grid)
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0
Output: 2Ans.
#include <bits/stdc++.h>
using namespace std;
int min(int a,int b)
{
if(a<b)return a;
else return b;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int r,c;
cin>>r>>c;
int a[r][c];
for(int i = 0;i<r;i++)
for(int j = 0;j<c;j++)
cin>>a[i][j];
int m = r,n=c;
int hp[m+1][n+1];
for(int i = 0;i<m+1;i++)
for(int j = 0;j<n+1;j++)
hp[i][j] = INT_MAX;
hp[m][n-1]=1;
hp[m-1][n]=1;
for(int i = m-1;i>=0;i--)
for(int j = n-1;j>=0;j--)
{
int need = min(hp[i+1][j],hp[i][j+1])-a[i][j];
if(need<=0) hp[i][j]=1;
else
hp[i][j]=need;
}
cout<<hp[0][0]<<endl;
}
return 0;
}- Given a non-empty array of integers arr, every element appears twice except for one. Find that single element. Implement this in linear time and no extra space.
Arr[] = {2,2,3}
Ans.#include <bits/stdc++.h> using namespace std; int singleNumber(vector<int>& nums) { int xor1 = nums[0]; for(int i = 1;i<nums.size();i++) xor1 = xor1^nums[i]; return xor1; } int main() { // your code goes here int n; cin>>n; vector<int> v(n); for(int i = 0;i<n;i++) cin>>v[i]; cout<<singleNumber(v)<<endl; return 0; } - Given a list of nodes from 0 to n-1 and respective edges you have to find the shortest distance between the source node (0) to every other node connected to it. The graph is undirected.
Input: 4(number of nodes) 4(number of edges)
0 1
0 3
1 2
2 3
Edge list
Output:
0 1 3 2 (distance of each node from 0)Ans.
#include <bits/stdc++.h>
using namespace std;
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *createAdjMatrix(int V,int E) {
struct Graph* G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;i<G->V;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;i<G->E;i++)
{
int u,v;
cin>>u>>v;
G->Adj[u][v] = 1;
G->Adj[v][u] = 1;
}
return G;
}
void BFS(struct Graph* G,int u,bool* visited){
queue<int> q;
q.push(u);
visited[u] = true;
while(!q.empty()){
int currentVertex = q.front();
q.pop();
cout<<currentVertex<<" ";
for(int i = 0;i<G->V;i++)
{
if(i==currentVertex)
continue;
if(!visited[i] && G->Adj[currentVertex][i])
{
q.push(i);
visited[i] = true;
}
}
}
}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;i<G->V;i++)
visited[i] = false;
for(int i = 0;i<G->V;i++)
if(!visited[i])
BFS(G,i,visited);
}
int main() {
int V, E;
cin >> V >> E;
struct Graph *G = createAdjMatrix(V,E);
BFSutil(G);
return 0;
}- You are again given an edge list and this time also given the weights of each edge and now again you have to find the shortest distance of the source node (0) to all other nodes.
Node Node Weight 0 1 2 0 4 5 1 3 9 1 5 1 2 3 1 2 4 3 3 5 2 3 4 7 Output: (node distance) 0 0 1 2 2 6 3 5 4 5 5 3Ans.
#include<bits/stdc++.h> using namespace std; class Graph{ unordered_map<int,list<pair<int,int>>> m; public: void addEdge(int x,int y,int w,bool bidir = true){ m[x].push_back(make_pair(y,w)); if(bidir) m[y].push_back(make_pair(x,w)); } void dijkstra(int src){ map<int,int> dist; set<pair<int,int>> s; for(auto node : m){ //marking all nodes dist as infinity dist[node.first] = INT_MAX; } dist[src] = 0; // for(auto ele : dist){ // cout<<ele.first<<" "<<ele.second<<endl; // } s.insert(make_pair(0,src)); while(!s.empty()){ auto distpair = *s.begin(); s.erase(s.begin()); int node = distpair.second; int nodedist = distpair.first; for(auto nbr : m[node]){ if(nodedist + nbr.second < dist[nbr.first]) { //update the distance auto f = s.find(make_pair(dist[nbr.first],nbr.first)); dist[nbr.first] = nodedist + nbr.second; if(f!=s.end()) s.erase(f); s.insert(make_pair(dist[nbr.first],nbr.first)); } } } for(auto ele : dist){ cout<<ele.first<<" "<<ele.second<<endl; } } }; int main(){ Graph g; g.addEdge(0,1,2); g.addEdge(0,4,5); g.addEdge(1,3,9); g.addEdge(1,5,1); g.addEdge(2,3,1); g.addEdge(2,4,3); g.addEdge(2,5,4); g.addEdge(3,5,2); g.addEdge(3,4,7); g.dijkstra(0); return 0; } - You are given a set of edges and nodes. These nodes are numbered from 0 to n-1, where n is the number of nodes. Again, we are given edges between these nodes and this time they are directed and you have to find the order of nodes in which each node will come such that no other nodes on which current node depends will not come faster. E.g., suppose there is an edge between 3->4 this means for getting node 4, node 3 has to be before 4.
Input: 8(nodes)
9(edges)
0 3
0 5
1 4
2 4
2 5
4 3
4 6
4 7
5 7
Edge listAns.
#include <bits/stdc++.h>
using namespace std;
struct Graph {
int V;
int E;
int** Adj;
};
struct Graph *createAdjMatrix(int V,int E) {
struct Graph* G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;i<G->V;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;j<G->V;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;i<G->E;i++)
{
int u,v;
cin>>u>>v;
G->Adj[u][v] = 1;
// G->Adj[v][u] = 1;
}
return G;
}
vector<int> BFS(struct Graph* G,int u,bool* visited){
priority_queue<int> q;
vector<int> topoVector;
vector<int> indegree(G->V,0);
for(int i = 0;i<G->V;i++){
for(int j = 0;j<G->V;j++)
{
if(G->Adj[i][j])
indegree[j]++;
}}
for(int i = 0;i<G->V;i++)
if(indegree[i]==0)
q.push(i);
while(!q.empty()){
int currentVertex = q.top();
q.pop();
visited[currentVertex] = true;
topoVector.push_back(currentVertex);
for(int i = 0;i<G->V;i++)
{
if(i==currentVertex)
continue;
if(!visited[i] && G->Adj[currentVertex][i])
{
indegree[i] = indegree[i] - 1;
if(indegree[i]==0)
q.push(i);
//visited[i] = true;
}
}
}
return topoVector;
}
vector<int> BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;i<G->V;i++)
visited[i] = false;
vector<int> v;
v = BFS(G,0,visited);
return v;
}
int main() {
int V, E;
cin >> V >> E;
struct Graph *G = createAdjMatrix(V,E);
vector<int> v = BFSutil(G);
for(auto i:v)
cout<<i<<" ";
return 0;
}- Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.
Input: arr = {4 3 1 0 5}, Output: 1 , start at position 4 and then to 5(last position)Ans.
#include <bits/stdc++.h> using namespace std; bool canJump(vector<int>& nums) { if(nums.size() == 0) return true; int midx = 0; for(int i = 0; i <= midx; ++ i){ midx = max(midx, i + nums[i]); if(midx >= nums.size()-1) return true; } return midx >= nums.size()-1; } int main() { vector<int> num1={4,3,1,0,5}; cout<<canJump(num1); return 0; } -
Given an array of integers where every element appears twice except two elements which appear once. You have to return these two elements.
Arr[] = [1 2 3 1 2 5]
Output: 3 5
Ans.#include <bits/stdc++.h> using namespace std; vector<int> solve(vector<int>& nums) { int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>()); // Get its last set bit diff &= -diff; // Pass 2 : vector<int> rets = {0, 0}; // this vector stores the two numbers we will return for (int num : nums) { if ((num & diff) == 0) // the bit is not set { rets[0] ^= num; } else // the bit is set { rets[1] ^= num; } } return rets; } int main() { int n; cin>>n; vector<int> arr(n); for(int i = 0;i<n;i++) cin>>arr[i]; vector<int> ans = solve(arr); for(auto ele : ans) cout<<ele[0]<<" "<<ele[1]<<endl; return 0; } - You must have played chess, don’t worry if you haven’t. A knight is a piece of chess which can move in some specific directions given by the arrows. You have to find out whether your Knight can travel to all cell in the grid or not. If it can travel to all cells then return true else false.
Input: N = 8
Output: 1 (knight can travel to all of the 64 cells)
Ans.#include <bits/stdc++.h> #define N 8 using namespace std; int mat[N][N]; //simple travelling that works for square matrix int row[N] = {2, 1, -1, -2, -2, -1, 1, 2 }; int col[N] = {1, 2, 2, 1, -1, -2, -2, -1 }; bool isValid(int r,int c){ return (r>=0 && c>=0 && r<N && c<N && mat[r][c] == -1); } bool knight_tour(int r,int c,int move){ if(move == N*N) return true; // base condition int move_x, move_y; for(int k = 0;k<N;k++){ move_x = r + row[k]; move_y = c + col[k]; if(isValid(move_x,move_y)){ mat[move_x][move_y] = move + 1; //storing the move number in matrix if(knight_tour(move_x,move_y,move + 1) == 1)return true; else mat[move_x][move_y] = -1;//backtracking } } return false; } int main() { // your code goes here memset(mat,-1,sizeof(mat)); mat[0][0] = 1; if(knight_tour(0,0,1)){//calling recur function //print the path matrix for(int i = 0;i<N;i++) { for(int j = 0;j<N;j++) cout<<mat[i][j]<<" "; cout<<endl; } } else cout<<"Not possible\n"; return 0; } - Do you know about LRU cache? Well, a LRU cache is basically a memory or data structure which stores the recently used objects for faster access next time. It implements two functions get and put, where get function returns the recently used in the cache and put inserts the new recently used object in the cache.
get(int key) Return the value of the key if the key exists, otherwise return -1.
put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Ans.int size; list<pair<int,int>> l; unordered_map<int,list<pair<int,int>>::iterator> m; //basics of this class We will implement the above two functions – int get(int key) { if(m.find(key)!=m.end()){ auto it = m.find(key); int val = it->second->second; if(it->second == l.begin())return val; l.erase(m[key]); l.push_front(make_pair(key,val)); m[key] = l.begin(); return val; } return -1; } void put(int key, int value) { //if the key is presetn int the list or not //if the key is present if(m.find(key)!=m.end()){ auto location = m[key]; l.erase(location); m.erase(key); } //if the key is not present and size is full if(m.size() == size){ int delkey = l.back().first; l.pop_back(); m.erase(delkey); } l.push_front(make_pair(key,value)); m[key] = l.begin(); //printlist();cout<<endl; } - In this problem we are given a binary string, simply a string of 0 and 1 and we are asked to reduce this number (which can be formed from this binary string) to 1 by following operations –
- If the number is even then divide it by 2
- If the number is odd then add 1 to it
Input: 101
101(5) -> 110(6) -> 011(3) ->100(4) -> 010(2) -> 001(1)
Output: 5
Return the number of steps if this is possible.
Ans.
#include <bits/stdc++.h>
using namespace std;
int steps(string s){
int step = 0;
while(s.size()>1){
if(s.back() == '0')//even
{
s.pop_back();
step++;
continue;
}
bool chk = false; //if we at all get any 0
for(int i = s.size()-1;i>=0;i--){
if(s[i] == '0'){
s[i] = '1';
chk = true;
break;
}
s[i] = '0';
}
if(!chk)s="1"+s;
step++;
}
return step;
}
int main()
{
//write your code here
string s;
cin>>s;
cout<<steps(s)<<endl;
return 0;
}- Implement a merge sort algorithm.
Ans.#include<bits/stdc++.h> using namespace std; //merges two sorted arrays void merge(int a[],int l,int m,int r){ int n1 = m-l+1; int n2 = r-m; int L[n1],R[n2]; for(int i=0;i<n1;i++){ L[i] = a[l+i]; } for(int i=0;i<n2;i++){ R[i] = a[m+i+1]; } int i=0,j=0,k=l; while(i<n1 && j<n2){ if(L[i]<=R[j]){ a[k++]=L[i++]; } else{ a[k++]=R[j++]; } } while(i<n1){ a[k++]=L[i++]; } while(j<n2){ a[k++]=R[j++]; } } //recursively performs merge sort void merge_sort(int a[],int l,int r){ if(l < r){ int m = l+(r-l)/2; merge_sort(a,l,m); merge_sort(a,m+1,r); merge(a,l,m,r); } } //wrapper for merge_sort void mergeSort(int ar_size,int a[]){ merge_sort(a,0,ar_size-1);} int main() { int ar_size = 5, i; int a[5] = {1, 5, 4, 3, 2}; mergeSort(ar_size, a); for(i=0; i<ar_size; i++){ cout<<a[i]<<" \n"[i==ar_size-1]; } return 0; } Output: 1 2 3 4 5 - Implement quicksort algorithm.
Ans.#include<iostream> using namespace std; // Partition int partition(int *array, int l, int r){ int pivot = array[r]; int i = l-1; // place for swapping for(int j = l; j <= r-1; j++){ if(array[j] <= pivot){ i++; swap(array[i], array[j]); } } swap(array[i+1], array[r]); return (i+1); } // Random pivot int partition_random_pivot(int *array, int l, int r){ srand(time(NULL)); int random = l + rand()%(r - l); swap(array[random], array[r]); return partition(array, l, r); } int quick_sort(int *array, int l, int r){ if(l < r){ // base case int pi = partition_random_pivot(array, l, r); // returns index of pivot quick_sort(array, l, pi-1); quick_sort(array, pi+1, r); } } int main(int argc, char const *argv[]){ int N; cout << "Enter the size of array:"; cin >> N; int A[N]; cout << "Enter the array elements:"; for(int i = 0; i < N; i++) cin >> A[i]; quick_sort(A, 0, N-1); cout << "Sorted array is: "; for(int i = 0; i < N; i++) cout << A[i] << " "; cout << endl; return 0; } - You are given an array which contains the price of stocks for each day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Price [] = [7 1 5 3 6 4]
Output: 7, which we can get from buying on day 2 and sell on day 3.
Ans.#include <bits/stdc++.h> using namespace std; int maxprofit(vector<int>& prices) { int profit=0; for(int i=1;i<prices.size();i++){ if((prices[i]-prices[i-1])>0){ profit+=prices[i]-prices[i-1]; } } return profit; } int main() { // your code goes here int n; cin>>n; vector<int> prices(n); for(int i = 0;i<n;i++) cin>>prices[i]; cout<<maxprofit(prices); return 0; } - Given an array of balloons which are painted with a number on it. You are asked to burst balloon such that your score increases by arr[left]arr[i]arr[right]. Left = i-1, right =i+1, after each burst the left and right balloons become adjacent. Find the maximum score by bursting balloons.
Arr[] = [4 1 5 10]
Output: 270
Ans.#include <bits/stdc++.h> using namespace std; int maxScore(vector<int>& nums) { if(!nums.size()) return 0; int n = nums.size(); nums.insert(nums.begin(), 1); nums.insert(nums.end(), 1); vector<vector<int>> dp(nums.size(), vector<int>(nums.size(), 0)); for(int len = 1; len <= n; ++ len ){ for(int start = 1; start <= n - len + 1; ++ start){ int end = start + len - 1; for(int i = start; i <= end; ++ i){ dp[start][end] = max(dp[start][end], dp[start][i - 1] + dp[i + 1][end] + nums[start - 1]*nums[i]*nums[end + 1]); } } } return dp[1][n]; } int main() { // your code goes here int n; cin>>n; vector<int> arr(n); for(int i = 0;i<n;i++) cin>>arr[i]; cout<<maxScore(prices); return 0; }