title: partition of array into k contiguous subarrays such that bitwise AND of sum of each subarray is maximum
body: <p>An array of size <code>n</code> (n&lt;=50) containing positive integers is given.
  You have to divide the array into <code>k</code> contiguous subarrays in such a way that the bitwise <code>AND</code> of all subarray sums is maximized.</p>
  
  <p>For example with <code>array=[30,15,26,16,21]</code> and <code>k=3</code>, consider all partitions:</p>
  
  <ul>
  <li>(30) &amp; (15) &amp; (26+16+21) = 14</li>
  <li>(30) &amp; (15+26) &amp; (16+21) = 0</li>
  <li>(30) &amp; (15+26+16) &amp; (21) = 16</li>
  <li>(30+15) &amp; (26+16) &amp; (21) = 0 </li>
  <li>(30+15) &amp; (26) &amp; (16+21) = 0</li>
  <li>(30+15+26) &amp; (16) &amp; (21) = 0</li>
  </ul>
  
  <p>Maximum of all is 16, so the answer for this array is 16.</p>
  
  <p>I am not getting any idea other than brute force. Please help.</p>
  
  <pre><code>static void findMaxAND(int[] arr,int k){
          if (k&gt;arr.length){
              System.out.println(0);
              return;
          }
          int n=arr.length;
          int[] parSum=new int[n];
          parSum[0]=arr[0];
          for (int i=1;i&lt;n;i++){
              parSum[i]+=parSum[i-1]+arr[i];
          }
  
          int upperSum=parSum[n-1]/k;
          int upperBit=(int)Math.floor((Math.log10(upperSum)/Math.log10(2)));
  
          partitions=new ArrayList&lt;&gt;();
          while (true){
              int min=(int)Math.pow(2,upperBit);
  
              check(arr,min,-1,new ArrayList&lt;&gt;(),1,k);
              if (!partitions.isEmpty()){
                  int maxAND=Integer.MIN_VALUE;
                  for (List&lt;Integer&gt; partiton:partitions){
                      partiton.add(n-1);
                      int innerAND=parSum[partiton.get(0)];
                      for (int i=1;i&lt;partiton.size();i++){
                          innerAND&amp;=(parSum[partiton.get(i)]-parSum[partiton.get(i-1)]);
                      }
  
                      maxAND=Math.max(maxAND,innerAND);
                  }
                  System.out.println(maxAND);
                  break;
              }
  
              upperBit--;
          }
      }
  
      private static List&lt;List&lt;Integer&gt;&gt; partitions;
  
      static void check(int[] arr,int min,int lastIdx,List&lt;Integer&gt; idxs,int currPar,int k){
          int sum=0;
          if (currPar==k){
              if (lastIdx&gt;=arr.length-1){
                  return;
              }
              int i=lastIdx+1;
              while (i&lt;arr.length){
                  sum+=arr[i];
                  i++;
              }
              if ((sum&amp;min)!=0){
                  partitions.add(new ArrayList&lt;&gt;(idxs));
              }
          }
          if (currPar&gt;k||lastIdx&gt;=(arr.length-1)){
              return;
          }
  
          sum=0;
          for (int i=lastIdx+1;i&lt;arr.length;i++){
              sum+=arr[i];
              if ((sum&amp;min)!=0){
                  idxs.add(i);
                  check(arr,min,i,idxs,currPar+1,k);
                  idxs.remove(idxs.size()-1);
              }
          }
      }
  </code></pre>
  
  <p>It is working but time complexity is too bad.</p>