ภารกิจคือการค้นหาสตริงย่อยจากสตริงไบนารีที่กำหนด จากนั้นจึงหาค่าความแตกต่างสูงสุดระหว่างจำนวนศูนย์กับจำนวนนั้น
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -
อินพุต
str = “10010110”
ผลลัพธ์
2
คำอธิบาย
ในอาร์เรย์ย่อยจากตำแหน่ง 1 ถึง 4 ("0010") ความแตกต่างระหว่างเลขศูนย์และอัน =3 – 1 =2 ซึ่งเป็นค่าสูงสุดที่หาได้
อินพุต
str = “00000”
ผลลัพธ์
5
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ในฟังก์ชัน main() ให้สร้างสตริง str เพื่อเก็บสตริงไบนารี ประกาศ anarray int arr . ด้วย [str.length()+1];
-
ตั้งค่าองค์ประกอบทั้งหมดของ arr[] =0 โดยใช้ memset(arr,0,sizeof(arr));
-
วนจาก j =1 ถึง j<=str.length()
-
ตรวจสอบ if(memset(arr,0,sizeof(arr)) ถ้าใช่ ให้ใส่ arr[j]=max(arr[j-1-1]-1,-1);
-
อย่างอื่นใส่ arr[j]=max(arr[j-1]+1,1);
-
นอกวงพิมพ์จำนวนสูงสุดโดยใช้ *max_element(arr+1,arr+str.length()+1);
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
int main(){
string str = "10010110";
int arr[str.length()+1];
memset(arr,0,sizeof(arr));
for(int j=1;j<=str.length();j++){
if(str[j-1]=='1')
arr[j]=max(arr[j-1]-1,-1);
else
arr[j]=max(arr[j-1]+1,1);
}
cout<<*max_element(arr+1,arr+str.length()+1);
return 0;
} ผลลัพธ์
2
