Given a positive integer array partition array into M subarray such that when we take sum of each subarray and chose maximum it is minimal across all subarray combinations.

I tried drawing all combinations when M=1, M=2... but couldn't find DP pattern. Some help will be greatly appreciated.

Input array : [7,2,3,4,5] and M = 3
Optimal partitioning : [7], [2,3,4], [5]
Answer Max(7, 2+3+4, 5) = 9

Input array : [4,3,2,2,2,6] and M = 3
Optimal partitioning : [4,3], [2,2,2], [6]
Answer Max(4+3, 2+2+2, 6) = 7

A string is called beautiful if string S = T + T. You're given a string find length of longest beautiful subsequence in given string.

Constraints : 1 <= length(S) <= 100

PS: Ihave no clue except try all numbers with k bits set and like bit-mask check if it's beautiful. Of-course you take k even and start from biggest possible k ie. length(S) - (length(S) & 1). Any hints on this ?

Hi, I am trying to solve a question. I understand the basic approach here using inclusion-exclusion principle but not able to understand what's happening in code at line 54 to 70. I understand that author of code is trying to place digits in empty places but why one loop(for i) starts from 0 and end at <dig_n-1 and why reverse after that(line 61) ? and similar kind of thing with j loop.

Problem editorial: here

Code take from here

Hi, I was solving Hard Problem and my approach is :

If string[i] <= string[i+1] than continue;

Else :

    If  string_rev[i] < string[i+1] c1=cost[i] Else c1=inf;

    If string[i] < string_rev[i+1] c2=cost[i+1] Else c2=inf;

    If string_rev[i] < string_rev[i+1] c3=cost[i]+cost[i+1]; Else c3=inf;

    if(c1<=c2 && c1<=c3 && c1!=inf) ans+=c1; If(c1==c2)a[i+1]=min(a[i+1],b[i+1]);;

    else if(c2<=c1 && c2<=c3 && c2!=inf) ans+=c2; a[i+1]=min(a[i+1],b[i+1]);

    else if(c3<=c1 && c3<=c2 && c3!=inf) ans+=c3; a[i+1]=min(a[i+1],b[i+1]);

Code Link.

Can you please help me in finding fault in this approach ?

On 26-March I had a coding round for Internship. Following were the 2 problems in that round :

Q1-> http://pastebin.com/KWjT8nJq

Q2-> http://pastebin.com/sa9VJkZF

My solution to question:

1-> http://pastebin.com/gzsDRNZK (RESULT : wrong answer)

In 2nd question naive solution gave TLE.

Can anyone please suggest new approaches or what test cases my code failed[Q1].

Thanks.