首页 > 代码库 > [003] largest_subarray_with_equal_1&0
[003] largest_subarray_with_equal_1&0
[Description] Given an array with only ‘1‘ and ‘0‘, find a largest length sub-array which contains equal number of ‘1‘ and ‘0‘. Return the largest number.
e.g. arr[] = {1,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,1}
return : 16
[Thought] Preprocess this array by add 1/-1 to arr[i] while arr[i] is 1/0; find the last position of ‘0‘ as ‘largest1‘; find the farther distance of the same number as ‘largest2‘; return the larger one of ‘largest1‘ and ‘largest2‘. O(n^2)
[Implementation] C code:
1 #include<stdio.h> 2 3 int largestSubarray(int str[],int size) 4 { 5 int largest=0; 6 int i,j; 7 str[0]?(str[0]=1):(str[0]=-1); 8 // preprocess. 9 for(i=1;i<size;i++)10 {11 str[i]?(str[i]=str[i-1]+1):(str[i]=str[i-1]-1);12 }13 // find the last 0‘s position, and find the farther distance of the same numbers.14 for(i=0;i<size;i++)15 {16 // find the last 0‘s position.17 if(0 == str[i] && (i+1)>largest)18 {19 largest=i+1;20 // printf("0:%d\n",largest);21 }22 // find the farther distance of the same numbers.23 for(j=0;j<i;j++)24 {25 if(str[i] == str[j] && (i-j)>largest)26 {27 largest=i-j;28 // printf("other:%d\n",largest);29 break;30 }31 }32 }33 return largest;34 }35 36 int main()37 {38 int str[]={1,0,1,0,0,0,1,1,0,1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,1};39 int size=sizeof(str)/sizeof(str[0]);40 int i;41 42 printf("Initianl Sequence which size is %d :\n",size);43 for(i=0;i<size;i++)44 {45 printf("%d, ",str[i]);46 }47 printf("\nlargest:%d\n",largestSubarray(str,size));48 }
[003] largest_subarray_with_equal_1&0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。