#include <bits/stdc++.h>
#define NMAX 305
using namespace std;
int n , k;
int cards[NMAX];
long long dp[NMAX][NMAX][NMAX / 2];
long long ans;


void maximize(long long &before , long long later)
{
        if(before < later)  before = later;
}


namespace sub1{

      int MaxLater[NMAX] , MinLater[NMAX] , two[NMAX];

      void codesub1()
      {
        if(k == 1)
        {
              for(int i = 1 ; i <= n ; i++) 
              for(int j = i + 1 ; j <= n ; j++)  maximize(ans , abs(cards[i] - cards[j]) );
        }

        if(k == 2)
        {
                 MaxLater[n] = MinLater[n] = cards[n];

                 for(int i = n - 1 ; i >= 1 ; i--)
                 {
                         MaxLater[i] = max(MaxLater[i + 1]  , cards[i]);
                         MinLater[i]  = min(MinLater[i + 1] , cards[i]);
                 }

                 for(int i = 2 ; i <= n ; i++)  two[i] = abs(cards[i-1] - cards[i]);

                 for(int i = 1 ; i <= n ; i++)  for(int j =  i + 1 ; j <= n ; j++)
                 for(int k = j + 1 ; k < n ; k++)
                       {
                           maximize(ans , abs(cards[i] - MaxLater[k + 1]) + abs(cards[j] - cards[k]) );

                           maximize(ans , abs(cards[i] - MinLater[k + 1]) + abs(cards[j] - cards[k]) );
                       }

                 for(int i = 2 ; i <= n ; i++)  
                 for(int j = i + 2 ; j <= n ; j++)  maximize(ans , two[i] + two[j]);
              }

            cout<<ans;
       }
}



namespace sub2{

   void backtrack(int LEFT , int RIGHT , int cnt , long long sum)
   {
        if(cnt == k)
        {
                maximize(ans , sum );
                return ;
        }

        backtrack(LEFT + 1 , RIGHT - 1 , cnt + 1 , sum + abs(cards[LEFT] - cards[RIGHT]));

        backtrack(LEFT + 2 , RIGHT , cnt + 1 , sum + abs(cards[LEFT] - cards[LEFT + 1]));

        backtrack(LEFT , RIGHT - 2 , cnt + 1 , sum + abs(cards[RIGHT] - cards[RIGHT - 1] ) );
   }

  void codesub2()
  {
        backtrack(1 , n , 0 , 0);

        cout<<ans;
  }

}

namespace sub3{

          void codesub3()
          {
                 for(int i = 1 ; i  <= n - 1 ; i++)  dp[i][i+1][1] = abs(cards[i] - cards[i+1]);

                 for(int cnt = 1 ; cnt <= k ; cnt++)
                 {
                         for(int length = 3 ; length <= n ; length++)
                         {
                                 for(int LEFT = 1 ; LEFT <= n - length + 1 ; LEFT++)
                                 {
            int RIGHT = LEFT + length - 1;

     maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT][RIGHT - 1][cnt]);

     maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 1][RIGHT][cnt]);

     maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT][RIGHT - 2][cnt - 1] + abs(cards[RIGHT] - cards[RIGHT - 1]));

     maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 2][RIGHT][cnt - 1] + abs(cards[LEFT] - cards[LEFT + 1]));

     maximize(dp[LEFT][RIGHT][cnt] , dp[LEFT + 1][RIGHT - 1][cnt - 1] + abs(cards[LEFT] - cards[RIGHT]));
                                 }
                         }
                 }

                cout<<dp[1][n][k];
          }

}

void process()
{
    cin>> n >> k ;
    for(int i = 1 ;  i<= n ; i++)  cin>>cards[i];

    if(n <= 300 && k <= 2)
    { 
        sub1::codesub1();
        
        return;
    }
    
    if(n <= 30 && 2 * k == n)
    { 
        sub2::codesub2();
        
        return;
    }
    
    sub3::codesub3();
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    process();
    return 0;
}