Mohammad Erfan Hossain's Blog

Simple dynamic problem!!! -- Take a 2D array size [105][105] -- calculate all set of product and store in array for future use. -- First fill diagonal element with input array elements. -- Then traverse diagonal wise, element value is array[i][j]= array[i][i]*array[i+1][j];     traversing end point at reaching array[0][n-1]; calculate max after calculating each product. import java.math.BigInteger; import java.util.Scanner; public class Main {     public static void main(String[] args) {         Scanner sc=new Scanner(System.in);         BigInteger max=BigInteger.valueOf(-999999);         BigInteger [][] arr=new BigInteger[105][105];         int x,n,i,j,y;         n=1;         while(sc.hasNext()){          x=sc.nextInt();          if(x!=-999999){         ...

#include<iostream> using namespace std; int arr[1005][1005],sum[1005][1005]; int main(){ freopen("test.txt","r",stdin); int i,j,k,m,n,temp; unsigned long long val; bool flag=false; while(cin>>n>>m){ if(flag) cout<<endl; flag=true; for(i=n-1;i>=0;i--) for(j=0;j<n;j++) cin>>arr[i][j]; sum[0][0]=0; for(i=0;i<m;i++) for(j=0;j<m;j++) sum[0][0]+=arr[i][j]; val=sum[0][0]; for(j=1;j<=n-m;j++){ temp=sum[0][j-1]; for(i=0;i<m;i++){ temp=temp-arr[i][j-1]+arr[i][j+m-1]; } sum[0][j]=temp; val=val+temp; } for(i=1;i<=n-m;i++){ for(j=0;j<=n-m;j++){ temp=sum[i-1][j]; for(k=j;k<j+m;k++){ temp=temp-arr[i-1][k]+arr[i+m-1][k]; } sum[i][j]=temp; val=val+temp; } } for(i=n-m;i>=0;i--) for(j=0;j<=n-m;j++) cout<<sum[i][j]<<endl; cout<<val<<endl; } ret...

Algorithm : Kadane Algo. #include<iostream> #include<vector> using namespace std; void kasane_algo(int *arr,int n,int &start_index,int &end_index){ int temp,i,diff,max; temp=max=arr[0]; start_index=0; vector<int> vec; if(temp>0){ vec.push_back(1); vec.push_back(2); } for(i=1;i<n;i++){ if(temp<0){ start_index=i; temp=0; } if(max<0 && arr[i]<0){ temp=-1; }else{ temp=temp+arr[i]; if(temp>=max){ if(temp>max){ vec.clear(); max=temp; } vec.push_back(start_index+1); vec.push_back(i+2); } } } diff=0; max=vec.size(); for(i=0;i<max;i=i+2){ if((vec[i+1]-vec[i])>diff){ diff=vec[i+1]-vec[i]; start_index=vec[i]; end_index=vec[i+1]; } } } int main(){ int arr[20001],i,kase,start_index,end_index,test_case,n; bool flag; cin>>kase; test_case=1; while(kase>=test_case){ cin>>n; flag=true...

Algorithm : Kadane's Algorithm (calculate max sum for sub array) Create 4 matrix for input matrix. Suppose input is 4*4 then store it 8*8 matrix. Suppose input 3*3 matrix a1 a2 a3 b1 b2 b3 c1 c2 c3 store it 6*6 matrix like a1 a2 a3 a1 a2 a3 b1 b2 b3 b1 b2 b3 c1 c2 c3 c1 c2 c3 a1 a2 a3 a1 a2 a3 b1 b2 b3 b1 b2 b3 c1 c2 c3 c1 c2 c3 calculate max sum for all 3*3 size matrix. Code: #include<iostream> #include<algorithm> using namespace std; int max_sum_sub_array(int *arr,int n){ int max,i,cur_sum; max=cur_sum=arr[0]; for(i=1;i<n;i++){ if(cur_sum<0) cur_sum=0; if(max<0 && arr[i]<0){ if(max<arr[i]) max=arr[i]; }else{ cur_sum=cur_sum+arr[i]; if(max<cur_sum) max=cur_sum; } } return max; } int main(){ int arr[160][160],i,j,k,n,kase,temp[160],max,ans,x,y; cin>>kase; while(kase--){ cin>>n; max=0x80000000; for(i=1;i<=n;i++){ for(j=1;j<=n;j++...

#include<iostream> using namespace std; void binary_search(int *arr,int start,int end,int val,int &pos){ if (start == end){ if (arr[start] > val) pos = start; else pos = -1; return; } int mid = (start + end) / 2; if (arr[mid] > val){ binary_search(arr, start, mid, val, pos); } else if (arr[mid + 1] > val){ pos = mid + 1; } else{ binary_search(arr, mid + 1, end, val, pos); } } int main(){ int arr[50001], pos, x, i, m, n,z; cin >> n; cin >> arr[0]; z = 0; for (i = 1; i < n; i++){ cin >> x; if (arr[z] != x){ z++; arr[z] = x; } } cin >> m; for (i = 0; i < m; i++){ cin >> x; if (z == 0){ if (arr[0] == x) cout << "X X" << endl; else if (arr[0] < x) cout << arr[0] << " X" << endl; else cout << "X " << arr[0] << endl; } else{ binary_s...